在一个旋转过的有序数组（比如3 4 5 1 2）上实现二分查找。
example:
11 12 13 14 15 16 17 18 19 20 4 5 6 7 8 9 10
suppose ascending from left to right
a_0 > a_n
a_m: middle position, m = (0 + n)/2
a_m > a_0 --> the left partial is ascending
a_m < a_n --> the right partial is ascending
b = 5
a_m = 19
a_m > a_0 > a_n > b --> b sits in the right partial
19 20 4 5 6 7 8 9 10
a_0 > a_n > a_m > b --> b sits in the left partial
19 20 4 5 6
a_0 > a_n > b > a_m --> b sits in the right partial
4 5 6
a_n == b
为何不找到分界点，然后判断在左侧还是右侧查找呢？
测试通过的算法
int binarysearch(int key, int* arr, int n)
{
int low = 0;
int high = n-1;
while(low<=high)
{
int mid = (low+high)/2;
if(arr[mid] == key)
return mid;
if(arr[mid]<key) low = mid+1;
else high = mid-1;
}
return -1;
}
int getoffset(int *arr, int n)
{
if(n<=1) return 0;
if(arr[0] <arr[n-1])return 0;
int low =0;
int high= n-1;
while(high-low>1)
{
int mid = (low+high)/2;
if(arr[mid] >=arr[low]) low = mid;
else high = mid;
}
return high;
}
int searchlooparray(int key, int * arr, int n)
{
int offset = getoffset(arr,n);
if(offset ==0) return binarysearch(key, arr, n);
if(key>=arr[0] && key <=arr[offset-1])
return binarysearch(key, arr, offset);
else if(key>=arr[offset] && key<=arr[n-1])
{
int result = binarysearch(key,arr+offset, n-offset);
return result==-1 ? result:offset + result;
}
else return -1;
}
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/clearriver/archive/2009/07/22/4371767.aspx