要搜索的对象是一个rotated sorted array，所以从直觉上时间复杂度应该不会超过O(logn)。起初我想尝试修改binary search来解决这个问题，但仔细思考后发现在不断search的过程中，search的boundary是比较难确定的。解决这个题目的另一个思路就是先把pivot找出来，在这里我把pivot定义为数组中最小的那个数。所以下面要解决的便是能不能在O(logn)的时间找到pivot。沿着这个思路，然后综合rotated sorted array的特征，可以用类似binary serach的方法找到pivot。pivot具有如下特征：pivot左侧和右侧的数均大于pivot本身。而搜索方向的确定可以根据比较当前搜索到的数与A[0]来判断，如果A[current] >= A[0]说明pivot在[current,n]的范围内，反之pivot在[0,current-1]范围内。不过要注意没有pivot的特殊情况，即array是sorted但没有被rotated。
在得到pivot后，我们便可以在pivot划分的两个区域内分别用binary search搜索target。时间复杂度为O(logn)。
1 class Solution { 2 public: 3 int search(int A[], int n, int target) { 4 int pivot = search_pivot(A,0,n-1); 5 if(pivot == -1) return binary_search(A,0,n-1,target); 6 if(target > A[pivot-1] || target < A[pivot] || target < A[0] && target > A[n-1]) return -1; 7 if(target >= A[0]) return binary_search(A,0,pivot-1,target); 8 else return binary_search(A,pivot,n-1,target); 9 } 10 int search_pivot(int A[], int left, int right){ 11 if(left >= right) return -1; 12 int mid = (left + right)/2; 13 if(A[mid] < A[0]){ 14 if(A[mid-1]>A[mid]) return mid; 15 else return search_pivot(A, left, mid-1); 16 }else { 17 if(A[mid+1]<A[mid]) return mid+1; 18 else return search_pivot(A,mid + 1,right); 19 } 20 } 21 int binary_search(int A[], int left, int right, int target){ 22 if(left > right) return -1; 23 int mid = (left + right)/2; 24 if(A[mid] == target) return mid; 25 if(A[mid] > target) return binary_search(A,left,mid-1,target); 26 if(A[mid] < target) return binary_search(A,mid+1, right,target); 27 } 28 };
Search in Rotated Sorted Array I,布布扣,bubuko.com
Search in Rotated Sorted Array I
原文：http://www.cnblogs.com/Kai-Xing/p/3886975.html