（转载）旋转数组查找最简洁方法总结

百度搜了几篇，太多了代码，实则苦涩难懂。面试笔试宝典总结的很给力。突然不能访问。以下是从百度快照中扒出来的。

次二分查找>：二分查找算法有两个关键点：1）数组有序；2）根据当前区间的中间元素与x的大小关系，确定下次二分查找在前半段区间还是后半段区间进行。

仔细分析该问题，可以发现，每次根据low和high求出mid后，mid左边（[low, mid]）和右边（[mid, high]）至少一个是有序的。

a[mid]分别与a[left]和a[right]比较，确定哪一段是有序的。

如果左边是有序的，若x<a[mid]且x>a[left], 则right=mid-1；其他情况，left =mid+1；

如果右边是有序的，若x> a[mid] 且x<a[right] 则left=mid+1；其他情况，right =mid-1；

代码如下：

int binary_search_in_rotate_array(int a[], int n, int x) {
 int low = 0;
�0�2 int high = n-1; //注意上界
�0�2 while(low <= high) {
�0�2�0�2�0�2 int mid = low + ((high - low) >> 1); //可防止溢出；移位操作高效；
�0�2�0�2�0�2 if(a[mid] == x)
�0�2�0�2�0�2�0�2�0�2 return mid;
�0�2�0�2�0�2 if(a[mid] >= a[low]) {//左半段有序
�0�2�0�2�0�2�0�2�0�2 if(x < a[mid] && x >= a[low]) {
�0�2�0�2�0�2�0�2�0�2�0�2�0�2 high = mid -1;
�0�2�0�2�0�2�0�2�0�2 } else {
�0�2�0�2�0�2�0�2�0�2�0�2�0�2 low = mid + 1;
�0�2�0�2�0�2�0�2�0�2 }
�0�2�0�2�0�2 } else { //右半段有序
�0�2�0�2�0�2�0�2�0�2 if(x > a[mid] && x <= a[high]) {
�0�2�0�2�0�2�0�2�0�2�0�2�0�2 low = mid + 1;
�0�2�0�2�0�2�0�2�0�2 } else {
�0�2�0�2�0�2�0�2�0�2�0�2�0�2 high = mid -1;
�0�2�0�2�0�2�0�2�0�2 }
�0�2�0�2�0�2 }
�0�2 }
�0�2 return -1; // 找不到，则返回-1
}

（转载）旋转数组查找 最简洁方法 总结

（转载）旋转数组查找最简洁方法总结