이분검색(Binary Search)

알고리즘 책에 나와있는 pseudocode 참고
1. 문제: n개 키를 가진 정렬된 배열 S에 x가 있는지를 결정하라.
2. 입력: 양의 정수 n, 정렬된(비내림차순) 키의 배열 S(첨자는 1부터 n까지), 키 key
3. location, S에서 key가 있는 위치(만약 key가 S에 없으면 0)

소스
int location(int *s, int low, int high, int key)
{
 int mid;
 if( low > high )
  return -1;
 else
 {
  mid = (low + high)/2;
  if( s[mid] == key )
   return mid+1;
  else if( s[mid] < key )
  {
   low = mid + 1;
   return location(s, low, high, key);
  }
  else
  {
   high = mid - 1;
   return location(s, low, high, key);
  }
 }
}

void main()
{
 int s[] = {10, 12, 13, 14, 18, 20, 25, 27, 30, 35, 40, 45, 47};
 unsigned num;
 int key, idx;

 num = sizeof(s)/sizeof(s[0])-1;

 key = 10;
 idx = location(s, 0, num, key);
 if( idx == -1)
 {
  cout << "찾는 값이 없습니다." << endl;
 }
 else
 {
  cout << "찾는 값은 "<< idx << " 번째 입니다." <<endl;
 }
}