问题描述：已知有序数组a[N]， 从中间某个位置k（k未知，k=-1表示整个数组有序）分开，然后将前后两部分互换，得到新的数组，在该新数组的查找元素x。如：a[]={1,2,5,7,9,10,15}，从k=4分开，得到新数组a={9,10,15, 1,2,5,7}。
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 ",find(b, 5, 1)); 38 printf("%d ",find(b, 5, 0)); 39 printf("%d ",find(b, 5, 1)); 40 printf("%d ",find(b, 5, 1)); 41 printf("%d ",find(b, 5, 1)); 42 43 printf(" "); 44 printf("%d ",find(a, 7, 9)); 45 printf("%d ",find(a, 7, 10)); 46 printf("%d ",find(a, 7, 15)); 47 printf("%d ",find(a, 7, 1)); 48 printf("%d ",find(a, 7, 2)); 49 printf("%d ",find(a, 7, 5)); 50 printf("%d ",find(a, 7, 7)); 51 52 return 0; 53 }
参考了这个博客：
http://www.jobcoding.com/datastructure-and-algorithm/array/one-sorted-array/rotate_array/