資料結構

 1  #include <stdio.h>
 2  int counter; // counting comparison
 3  int binary_search(int arr[], int key, int left, int right) {
 4      int mid;
 5      if(left>right){
 6          counter++;
 7          return left;
 8      }
 9      if (key<arr[left]){ //left boundary
10          counter++;
11          return left;
12      }
13      if (key>=arr[right]){ //right boundary
14          counter++;
15          return right+1;
16      }
17      mid=(left+right)/2;
18      if (key<arr[mid].val){
19          counter++;
20          binary_search(arr,key,left,mid-1);
21      }
22      else { // (key>=arr[mid].val)
23          binary_search(arr,key,mid+1,right);
24      }
25  }
26  int main() {
27      int arr[9]={1,2,3,5,5,5,6,7,9};
28      counter=0;
29      int j=binary_search(arr,5,0,8);
30      printf("%d",j);
31      printf("%d",counter);
32  }