旋转数组的二分查找

 1 #include "stdafx.h"
 2 
 3 int search(int *a, int key, int low, int high)
 4 {
 5     if (low > high)
 6         return -1;
 7 
 8     int mid = (low + high)/2;
 9     if (key == a[mid])  
10         return mid;   
11     
12     if (a[mid] <= a[high])       //右边有序。
13     {
14         if(a[mid] < key && key <= a[high])      //在右边有序部分寻找。        
15             return search(a, key, mid + 1, high);    
16         else                                                //排除右边有序部分。          
17             return search(a, key, low, mid - 1);   
18     }
19     else                        //左边有序   
20     {
21         if(key < a[mid] && a[low] <= key)     //在左边有序部分寻找。              
22             return search(a, key, low , mid - 1);
23         else                                                //排除左边有序部分。      
24             return search(a, key, mid + 1, high);      
25     }   
26 }
27 
28 int find(int *a, int size, int key)
29 {    
30     return search(a, key, 0, size - 1);
31 }
32 
33 int _tmain(int argc, _TCHAR* argv[])
34 {
35     int a[] = {9, 10, 15, 1, 2, 5, 7};
36     int b[] = {1,0,1,1,1};
37     printf("%d\n",find(b, 5, 1));
38     printf("%d\n",find(b, 5, 0));
39     printf("%d\n",find(b, 5, 1));
40     printf("%d\n",find(b, 5, 1));
41     printf("%d\n",find(b, 5, 1));
42 
43     printf("\n");
44     printf("%d\n",find(a, 7, 9));
45     printf("%d\n",find(a, 7, 10));
46     printf("%d\n",find(a, 7, 15));
47     printf("%d\n",find(a, 7, 1));
48     printf("%d\n",find(a, 7, 2));
49     printf("%d\n",find(a, 7, 5));
50     printf("%d\n",find(a, 7, 7));
51 
52     return 0;
53 }