Binary Search

Binary Search란?

이진탐색은 분할 정복 기법을 이용하여 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다.

분할 정복 기법 (Divide and Conquer)

문제를 동일한 유형의 여러 서브 문제로 나누고, 가장 작은 단위의 서브 문제를 해결한 뒤, 그 결과를 원래 문제에 대한 결과로 조합하는 문제 해결 기법

과정

0. 리스트를 오름차순으로 정렬
1. 리스트의 중간 값과 찾는 값을 비교
2. 찾는 값이 중간 값이라면 해당 위치 반환
3. 찾는 값이 중간 값보다 작다면 중간 값보다 앞쪽에 위치한 서브 리스트에 대해 1번 과정부터 반복
4. 찾는 값이 중간 값보다 크다면 중간 값보다 뒤쪽에 위치한 서브 리스트에 대해 1번 과정부터 반복

분석

이진탐색은 원하는 값을 찾지 못한 경우 리스트를 반으로 나눠 그중 한 리스트에 대해 다시 이진탐색을 진행하므로 최악의 경우 탐색하는 리스트의 크기가 1이 될 때까지 분할을 진행합니다. 즉 이진탐색은 최대 O(log n) 만큼의 분할이 발생할 수 있고 각 단계에서 리스트의 중간 값과 한번 비교하므로 O(log n) 의 시간복잡도를 갖습니다.

재귀로 구현

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

반복문으로 구현

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