재귀 방식으로 이진 탐색하기.

이진 탐색을 재귀적인 방법으로 구현해 봤다.

"윤성우의 열혈 자료구조" 61페이지에 언급된 것을 스스로 구현해 봄.

  1 #include <stdio.h>
  2
  3 int main(int argc, char * argv[])
  4 {
  5         int arr[] = {3, 7, 9, 11, 25, 27, 30, 33};
  6         int target = 3;
  7         int first = 0;
  8         int len = sizeof(arr) / sizeof(int);
  9         int last = len - 1;
 10         bsr(arr, first, last, 3);
 11         bsr(arr, first, last, 7);
 12         bsr(arr, first, last, 9);
 13         bsr(arr, first, last, 11);
 14         bsr(arr, first, last, 25);
 15         bsr(arr, first, last, 27);
 16         bsr(arr, first, last, 30);
 17         bsr(arr, first, last, 33);
 18         bsr(arr, first, last, 34);
 19 }
 20
 21
 22 int bsr(int* arr, int first, int last, int target)
 23 {
 24
 25         int mid = (first + last) / 2;
 26
 27         if(first > last)  {
 28                 printf("not found %d %d\n", first, last);
 29                 return -1;
 30         }
 31
 32         if(arr[mid] == target) {
 33                 printf("found %d %d\n", mid, arr[mid]);
 34                 return mid;
 35         } else if (arr[mid] < target) {
 36                 printf("ele less than target (%d %d)\n", mid+1, last);
 37                 return bsr(arr, mid+1, last, target);
 38         } else if (arr[mid] > target) {
 39                 printf("ele greater than target (%d %d)\n", mid+1, last);
 40                 return bsr(arr, first, mid-1, target);
 41         }
 42 }