Copyright (c) 2015-, All Rights Reserved by Kwanghoon Choi
(아래 강의 노트를 자유롭게 이용하되 다른 웹 사이트 등을 통한 배포를 금합니다.)

The C Programming Language 2nd Ed. by Kerninghan & Ritchie ( Ch.3, binsearch )

이진 탐색(binary search)은 정렬된 숫자들에서 지정한 숫자가 있는지 찾는 방법이다. 탐색 대상이 이미 정렬되어 있는 성질을 이용하면 앞에서 부터 하나씩 확인해보는 순차 탐색 보다 더 적은 비교 횟수만으로 지정한 숫자를 찾거나 없음을 확인할 수 있다.

아래는 이진 탐색을 구현하는 한가지 꼬아놓은 방법이다. 보통 책에서 나오는 이진 탐색 구현은 아래의 방법과 유사한 방법을 사용하지만 while 루프 내 if 구조가 다르다. 즉 if (x < v[mid]) high = mid-1; else if (x > v[mid]) low = mid+1; else return mid; 를 보통 사용한다. 보통의 방법과 비교하면 아래의 방법은 while 루프 내에서 if 테스트를 한번만 한다. (단. while 루프 밖의 return에서 if 테스트를 한번 한다.)

이 구현 방법이 원래의 이진 탐색과 동일하게 동작할까?

int binsearch(int x, int v[], int n)
{
  int low, high, mid;

  low = 0;
  high = n-1;
  
  while(low < high) {
    mid = (low+high)/2;
    if(x <= v[mid]) 
      high = mid;
    else 
      low = mid+1;
  }
  
  return (x == v[low])?low : -1;

} 

위 구현이 이진 탐색을 하는지 확인하려면 프로그램 문장을 처음부터 끝까지 하나씩 따라가면서 확인하면 된다. 하지만 low = 0나 high = n-1, 마지막 return 문의 경우 따라가기 쉬운데 while 루프는 그렇지 않다. 왜냐하면 while 루프가 몇 번 반복하느냐에 따라서 따라가야 하는 문장의 수가 달라지기 때문이다. 사실 while 루프는 입력 (binsearch 함수의 인자) x, v, n이 무엇이냐에 따라 0번 반복되거나, 1번 반복되거나, 임의의 k번 반복될 수 있다.

while 루프가 몇 번 반복하는지 모르는 상황에서 while 루프 내의 문장을 따라가는 방법이 있을까? 다행히 있다! while 루프의 반복 횟수에 무관하게 항상 참인 성질을 찾아낸다면 반복 횟수가 중요하지 않게 된다. 그러한 성질을 루프 불변 명제 (Loop Invariant)라고 부른다.

위 while 루프의 루프 불변 명제는 무었일까? 단, n>=1이라고 가정한다. v[0] <= v[1] <= ... <= v[n-2] <= v[n-1]을 가정한다.

• [P]   0 <= low <= high <= n-1

P가 루프 불변 명제인지 검증해보자. 먼저, 맨 처음 while 루프로 진입할 때 low=0이고 high=n-1이므로 P가 성립한다.

그 다음, P가 성립하고 low < high일 때 while 루프 안의 문장을 하나씩 실행해보자. 즉 0 <= low < high <= n-1이다. high = low + k (k>=1)로 놓을 수 있다. 따라서 mid = (low + high)/2 = (low + low + k) / 2 = low + k/2  (k>=1)

i) x <= v[mid] : high = mid = low + k/2

k>=1이면 low <= low + k/2이다. low <= high가 참이다. 따라서 P가 성립.

ii) x > v[mid] : low = mid + 1 = low + 1 + k/2

k>=1이면 low + 1 + k/2 <= low + k (k=1,2,3,4,...일때 확인) 따라서 low <= high가 참이다. 따라서 P가 성립.

i)과 ii) 어느 경우든 P가 성립한 상황에서 while 루프 내 문장을 모두 실행하면 다시 P가 성립함을 알 수 있다.

while 루프를 빠져 나오면 ~(low < high)이고 P (특히, low<=high)이므로 둘 다 성립하려면 low == high이다. v[low] 또는 v[high]가 x와 같으면 x를 찾았으므로 low 또는 high를 리턴한다. 그렇지 않으면 -1을 리턴한다.

[끝]