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.

相当于将数组的后面一部折叠到数组的前面去了，本质上也是二分法，这里其实也是有规律可循的：首先要得到转折点，也就是其左边右边都比其大的那一点。给一个start以及一个end，如果nums[mid] > nums[start]，那么说明从start到mid也一定是递增的，很容的知道pivot一定在mid+1到end之间，那么递归的去查找就可以了。nums[mid] < nums[start]可以同样的去分析，代码如下所示：

1 class Solution { 2 public: 3     int search(vector
     
      & nums, int target) { 4         int pivot = getPivot(nums, 0, nums.size() - 1); 5         int pos = bSearch(nums, 0, pivot - 1, target); 6         if(pos != -1) 7             return pos; 8         return bSearch(nums, pivot, nums.size() - 1, target); 9     }10     11     int getPivot(vector
      
       &nums, int start, int end){12         if(start > end)13             return -1;14         int mid = start + (end - start)/2;15         if(nums[start] <= nums[mid]){16             int pos = getPivot(nums, mid + 1, end);17             if(pos == -1) return start;18             else19                 if(nums[pos] < nums[start])20                     return pos;21                 else22                     return start;23         }else{24             int pos = getPivot(nums, start, mid);25             if(pos == -1)26                 return mid;27             if(nums[pos] < nums[end])28                 return pos;29             else30                 return mid;31         }32     }33     34     int bSearch(vector
       
        &nums, int start, int end, int target){35        int mid;36        while(start <= end){37            mid = (start+end)/2;38            if(nums[mid] > target){39                end = mid - 1;40            }else if(nums[mid] < target){41                start = mid + 1;42            }else{43                return mid;44            }45        } 46        return -1; //返回-1，表明在这一部分没有找到，可以在下一部分查找47     }48 };