[Algorithm] 이진 탐색(Binary search)

이진 탐색이란?

• 이진 탐색은 정렬된 리스트에서 검색 범위를 절반씩 줄여 나가며 검색 데이터를 탐색하는 알고리즘입니다.
• 정렬된 리스트에서만 사용할 수 있다는 단점이 있지만 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있습니다.
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾는 방식으로 동작합니다.
  1. 배열의 중간 데이터를 비교
  2. 중간 데이터와 검색 데이터를 비교
     1. 중간 데이터가 검색 데이터와 같다면 종료
     2. 중간 데이터보다 검색 데이터가 크다면 중간 데이터 기준 배열의 오른쪽 구간을 대상으로 탐색
     3. 중간 데이터보다 검색 데이터가 작다면 중간 데이터 기준 배열의 왼쪽 구간을 대상으로 탐색
  3. 데이터를 찾을 때까지 2번 작업을 반복

예제

key = 23

1. Low = 10, Mid = 21, High = 42

2. Low = 23, Mid = 33, High = 42

3. Low = 23, Mid = 23, High = 23 (탐색 완료)

시간 복잡도

이진 탐색을 반복할수록 남아있는 자료의 개수는 절반이 됩니다. (N/2, 1/2 * N/2, 1/2 * 1/2 * N/2 ...)
K번의 탐색 = (1/2)^K * N이되고 K = log2N입니다.
따라서 시간복잡도는 O(logN)입니다.

구현 (Java)

1. 반복문

   public static int binarySearch(int[] arr, int key) {
   var low = 0;
   var high = arr.length - 1;
   
   while (low <= high) {
    var mid = (high + low) / 2;
    if (arr[mid] == key) {
      return mid;
    } else if (arr[mid] > key) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
   }
   
   return -1;
   }

2. 재귀

   public static int binarySearch(int[] arr, int low, int high, int key) {
   if (high < low) {
    return -1;
   }
   
   var mid = (high + low) / 2;
   if (arr[mid] == key) {
    return mid;
   } else if (arr[mid] > key) {
    low = mid + 1;
   } else {
    high = mid - 1;
   }
   
   return binarySearch(arr, low, high, key);
   }