이진탐색 ( 이분탐색, Binary Search)의 모든 것

1. Introduction

이진탐색은 정렬된 리스트에 적용할 수 있는 간단한 고속 탐색 기법이다.

해시 같은 매핑 기반의 기법을 제외한다면 가장 빠른 탐색 속도를 보장한다.

---

2. Method

이진탐색의 핵심은 전체 탐색범위를 반으로 나눠서 찾고자 하는 원소 (이하 target, $T$)가 없을 것으로 기대되는 쪽을 버리는 것이다. 이를 통해 탐색범위는 기존의 탐색범위의 $1\over2$이 되고, 이 새로운 탐색 범위에 반을 버려가는 과정을 반복하여 결과적으로 target을 찾아내는 방법이다.

과정을 자세하게 알아보자.

1. 탐색을 원하는 구간 [a, b]에 대해 a를 low, b를 high라고 하자. (당연히 low, high는 index이다)
2. low와 high의 중간 값을 mid라고 하자.
3. 탐색할 리스트를 temp라고 하면 temp[mid]와 target의 값을 비교한다. (즉, value끼리 비교한다)
4. target이 크다면 mid가 새로운 low가 된다 (즉, 왼쪽반을 버림). target이 작다면 반대로. 
5. 1~4를 반복
6. 만약 temp[mid]와 target이 같다면 mid를 return.
7. low와 high가 같을 때까지 못 찾았다면 error (false, -1등 다양함)를 return.

이 과정을 이미지를 통해 시각적으로 이해해보자.

Average-case of Binary Search

 

Worst-case of Binary Search

 

Best-case of Binary Search

 

다음은 recursive한 이진 탐색의 pseudo-code이다.

BinarySearch(A[0..N-1], target, low, high) {
  if (high <= low)
    return -1 // not found
  mid = (low + high) / 2
  if (A[mid] > target)
    return BinarySearch(A, target, low, mid-1)
  else if (A[mid] < value)
    return BinarySearch(A, target, mid+1, high)
  else
    return mid // found
}

 

다음은 non-recursive한 이진 탐색의 pseudo-code이다.

BinarySearch(A[0..N-1], target, low, high) {
  for (low <= high) 
    mid = (low + high) / 2
    if (A[mid] < target)
      low = mid + 1
    else if (A[mid] > target)
      high = mid - 1
    else
      return mid // found

  return -1 // not found
}

---

3. Evaluation

• Best-case Performance   : $O(1)$
• Worst-case Performance : $O(log\; n)$
• Average Performance      : $O(log\; n)$
• Space Complexity            : $O(1)$ (non-recursive),  $O(log\; n)$ (recursive)

---

4. Discussion

가끔 보다보면 mid 값을 설정할 때, 단순히 $mid \; = \; {(low \; + \; high) \over 2}$가 아니라 $low \; + \; {(high \; - \; low) \over 2}$를 주는 경우를 볼 수 있다.

이것은 약간의 산술 연산을 더해서 low + high가 overflow 나는 경우에도 코드가 동작할 수 있도록 짠 것이다.

또 매 iteration마다 a[mid]가 target과 같은지 확인하고 있는데 이 부분을 빼고 항상 low가 high와 같아질 때까지 돌리고 마지막에 한번만 a[mid]가 target과 같은지 확인해도 된다. 이 방법은 기존 코드의 alternative한 방법으로 뒤에서 더 자세하게 다룬다.

a 배열이 만약 중복이 허용된 배열이라면, 이진 검색으로 Target을 찾는데에 오류는 없지만 그 결과가 항상 중복 원소의 첫번째 위치를 보장해주지는 않는다. 첫번째 위치를 찾는 일은 종종 쓸모가 있는데 (e.g. Rank), 이 경우 가장 중복 원소의 가장 왼쪽 자리 (leftmost element)를 찾아야 한다. 이 때, 위의 alternative한 방법을 쓴다 (가장 오른쪽 자리도 마찬가지). 

이진검색은 정렬된 배열에서 원하는 원소를 탐색하는 기법이므로 Approximate match가 가능하다.

• Predecessor (전위자)는 leftmost element의 결과값 r에대해, r-1과 같다.
• Successor (후위자)는 rightmost element의 결과값 r에 대해, r+1과 같다.
• Rank는 leftmost element의 결과와 같다.
• Nearest element는 Predecessor과 Successor중에 더 가까운 값과 같다.
• Range query (범위 안에 해당하는 값들에 대한 인덱스)는 범위 (a, b)에 대해 a의 Successor부터 b의 Predecessor까지의 인덱스와 같다.