[알고리즘] 이분 탐색(이진탐색) - BinarySearch

이분 탐색(이진탐색) 알고리즘 은 찾을 범위를 반으로 나눠서 탐색하는 알고리즘이다.

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 키값의 크고 작음을 비교하는 방식이다. 처음 선택한 중간값이 만약 찾는 값보다 크면 최댓값이 되고, 작으면 최솟값이 된다.

 

- 분할 정복 알고리즘에 속하는 알고리즘이다. 

- 단, 이미 정렬된 경우에만 적용할 수 있다.

- 최악의 경우는 찾으려는 키값이 배열에 존재하지 않을 때이다.

- 시간복잡도는 O(logN) 이다.

 

 

반복문을 사용하는 경우

int BinarySearch(int arr[], int length, int key){
	int first = 0;
    	int last = length - 1;
    	int mid = 0;
    
        while(first <= last){
            mid = (first+last)/2;
            if(arr[mid] > key){ // 중간값이 찾으려는 키값보다 크다면
                last = mid - 1;
            }else if(arr[mid] < key){ // 중간값이 찾으려는 키값보다 작다면
                low = mid + 1;
            }else{ // 중간값과 찾으려는 키값이 같다면
                return mid;
            }
        }
        return -1; // 키값을 못찾으면 -1을 리턴
}

 

재귀호출을 사용하는 경우

int BinarySearch(int arr[], int key, int first, int last){
      int mid = 0;

      if(first>last){
          return -1;
      }else{
          mid = (first+last)/2;
          if(arr[mid] == key){
              return mid;
          }else if(arr[mid] < key){
              BinarySearch(arr, key, first, mid-1);
          }else{
              BinarySearch(arr, key, mid+1, last);
          }
      }
}