5주차 : 이진탐색

참조

정의

이진탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘.
배열의 중간에 있는 임의의 값을 선택하여 찾고자하는 값 X와 비교한다. X가 중간값보다 작으면 중간 값을 기준으로 좌측의 데이터를 대상으로 중간값보다 크면 우측을 대상으로 재탐색한다.

해당 코드는

• 반복문을 이용하거나
• 재귀함수를 이용하여 구현할 수 있다.

-> 반복문 이용

int BSearch(int arr[] , int target){
	int low = 9;
    int high = arr.length -1l
    int mid;
    
    while(low<= high){
		mid = (low+high) /2;
        if(arr[mid] == target){
        	return mid;{
        else if(arr[mid] > target){
        	high = mid -1;}
        else{ low = mid +1;}
        }
    return -1;
    }

-> 재귀함수 이용

int BSearchRecursive(int arr[], int target, itn low, int high){
	if(low>high) return -1;
    int mid = (low+high)/2;
    
    if(arr[mid] ==target) return mid;
    else if(arr[mid] > target) return BSearchRecursive(arr, target, low, mid-1);
    else return BSearchRecursive(arr, target, mid+1,high);}