本文共 2229 字，大约阅读时间需要 7 分钟。
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
两层的二分查找，最外层的二分用来找到有序的部分，因为初始有序的数组被翻转后，其中的任何位置的元素都仍然属于一个有序的子序列，这个有序的子序列不是在左边有序，就是右边有序，当然也可能都有序。
里层的二分查找就简单了，就是我们所谓的二分查找，在一个有序的序列中查找给定值。
class Solution {public: int search(int A[], int n, int target) { if(n == 0) return -1; int left = 0, right = n - 1; while (left <= right) { int midle = (left + right) >> 1; //右半部分有序 if (A[midle] <= A[right]) { //右半部分包含目标值？ if(A[midle] <= target && target <= A[right]) { int rlow = midle, rhigh = right; while (rlow <= rhigh) { int mid = (rlow + rhigh) >> 1; if(A[mid] == target) return mid; else if(A[mid] < target) rlow = mid + 1; else rhigh = mid - 1; } } right = midle - 1; } //左半部分有序 if(A[left] <= A[midle]) { //左半部分包含目标值？ if (A[left] <= target && target <= A[midle]) { int llow = left, lhigh = midle; while (llow <= lhigh) { int lmid = (llow + lhigh) >> 1; if(A[lmid] == target) return lmid; else if(A[lmid] < target) llow = lmid + 1; else lhigh = lmid - 1; } } left = midle + 1; } } return -1; }}; 这代码写的用宋丹丹的话说“那是相当的难看”，很丑陋，不简洁，但是思路比较清晰，就是先判断左右部分是否有序，只有有序，我们才能对其使用二分查找，当然，在进行里层的二分查找前，我们判断这个有序的子序列是否包含目标值，若包含，则进行二分查找，若不包含，那就算了。
class Solution {public: int search(int A[], int n, int target) { if(0 == n) return -1; int left = 0; int right = n - 1; while(left <= right) { int midle = (left + right) >> 1; if(A[midle] == target) return midle; if(A[left] <= A[midle]) { if(A[left] <= target && target < A[midle]) { right = midle - 1; } else left = midle + 1; } else{ if(A[midle] < target && target <= A[right]) left = midle + 1; else right = midle - 1; } } return -1; }}; 精简点的。 转载地址：http://aelji.baihongyu.com/