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.
思路：
因为没有重复元素，所以情况变得比较简单，要么递增，要么就是如下情况：A[0] < A[n]，同时存在一点A[k] > A[k - 1]并且A[k] > A[k + 1]。
/ (k) / / / (start) / (end) / / (k + 1)
对于A[start] < A[end]的情况很简单，直接二分法搞定。对于后一种情况，先找到k点，然后确定target在A[start]到A[k]的区间还是A[k + 1]到A[end]的区间，因为每个区间都是递增的，也可以用二分法搞定。整个题目的难点在于如何用二分法找到k点。
- 如果区间只有一个元素就直接返回。
- 如果A[end] > A[start]，说明是个递增序列，返回end。
- 如果A[start] > A[start + 1]，返回start。
- 令mid等于(start + end) / 2。
- 如果A[mid] < A[end]，说明mid在k + 1到end的区间，那么k就在start在mid - 1的区间，递归调用，令start不变，end等于mid - 1。
- 如果A[mid] > A[start]，说明k在mid到end的区间，递归调用，令start等于mid，end不变。
1 class Solution { 2 public: 3 int findPivot(int A[], int start, int end) { 4 if (start == end) { 5 return start; 6 } 7 else if (A[end] > A[start]) { 8 return end; 9 }10 else if (A[start] > A[start + 1]) {11 return start;12 }13 14 int mid = (start + end) / 2;15 16 if (A[mid] < A[end]) {17 return findPivot(A, start, mid - 1);18 }19 else if (A[mid] > A[start]) {20 return findPivot(A, mid, end);21 }22 }23 24 int binarySearch(int A[], int start, int end, int target) {25 while (start <= end) {26 int mid = (start + end) / 2;27 28 if (A[mid] == target) {29 return mid;30 }31 else if (A[mid] < target) {32 start = mid + 1;33 }34 else {35 end = mid - 1;36 }37 }38 39 return -1;40 }41 42 int search(int A[], int n, int target) {43 int pivot = findPivot(A, 0, n - 1);44 45 return (target >= A[0]) ? binarySearch(A, 0, pivot, target) : binarySearch(A, pivot + 1, n - 1, target);46 }47 };