[필수 알고리즘] 이분 탐색(Binary Search) 이해

이분/이진 탐색 Binary Search

정렬 등과 함께 가장 기초인 알고리즘으로 꼽히는 문제.

이진 탐색은 오름차순으로 정렬된 리스트에서 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다.

 

이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만,

검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있다.

 

이진 탐색 기법 활용

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 사용한다.

이때, 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.

1. 배열의 중간 값을 가져온다.
2. 중간 값과 검색 값을 비교한다.
   1. 중간 값이 검색 값과 같다면 종료한다. (mid = key)
   2. 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색한다. (mid < key)
   3. 중간 값보다 검색 값이 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색한다. (mid > key)
3. 값을 찾거나 간격이 비어있을 때까지 반복한다

 

활용 예시

key 값 39를 찾아보자.

1. 배열의 중간 값을 가져온다. (low = 0, high = 9, mid =4)

mid  = low + (high - low) / 2
          = 0 + (9-0)/2
          = 4

중앙값과 검색 값을 비교합니다.

A [4] (27) < key (39) 이므로 배열의 오른쪽 구간을 검색 범위로 정한다.

 

2. 배열의 중간 값을 가져온다. (low = 5, high = 9, mid = 7)

mid  = low + (high - low) / 2
          = 5 + (9-5)/2
          = 7

 중앙 값과 검색 값을 비교합니다.

A [7] (45) > key (39) 이므로 배열의 왼쪽 구간을 탐색 범위로 정한다.

 

3. 중앙 값을 결정  (low = 5, high = 6, mid = 5)

mid  = low + (high - low) / 2
        = 5 + (6-5)/2
        = 5

중앙값과 검색 값을 비교합니다.

A [5] (32) < key (39) 이므로 배열의 오른쪽 구간을 탐색 범위로 정한다.

그러고 나면 배열의 요소는 1개만 남았으므로 39가 되고 우리가 찾으려는 값과 일치하게 된다.

 

최악의 경우에는 배열의 사이즈가 1이 될 때까지 반으로 쪼개는 것이므로 (1 / 2) k * N = 1이고, 

양변에 로그를 취하여 정리하면, log2N이 되는 것을 알 수 있다.

따라서, 이진 탐색의 시간 복잡도는 O(logN) 이다.

 

종료조건

이진 탐색의 종료 조건은 두 가지가 있다.

다음 조건중 하나라도 성립하면 검색을 종료된다.

 

1. 검색을 성공할 경우

• 리스트에서 검색할 값과 같은 요소를 발견한 경우
• a [mid] == key

2. 검색을 실패한 경우

• 더 이상 검색할 범위가 없을 경우
• low > high

 

구현

반복문을 이용한 방법

public static int binarySearch(int arr[], int find) {
  int mid;
  int left = 0;
  int right = arr.length - 1;

  // 배열의 크기가 1이 될 때까지 반복.
  while (left <= right) {
    mid = (right + left) / 2;

    // 원하는 값을 찾았다면 그 위치를 반환.
    if (arr[mid] == find) {
      return mid;
    }

    if (find < arr[mid]) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  // 원하는 값을 찾지 못함.
  return -1;
}

 

재귀 함수를 이용한 방법

public static int binarySearch(int[] arr, int find, int left, int right) {
  // 원하는 값을 찾지 못함.
  if (left > right) {
    return -1;
  }

  int mid = (left + right) / 2;
  
  // 원하는 값을 찾았다면 그 위치를 반환.
  if (find == arr[mid]) {
    return mid;
  }

  if (find > arr[mid]) {
    return binarySearch(arr, find, mid + 1, right);
  }
  return binarySearch(arr, find, left, mid - 1);
}