题目：
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,0 1 2 4 5 6 7might become4 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.
说明：
1）已排序数组查找采用二分查找
2）关键找到临界点
实现：
一、我的代码：
1 class Solution { 2 public: 3int search(int A[], int n, int target) { 4 if(n==0||n==1&&A[0]!=target) return -1; 5 if(A[0]==target) return 0; 6 int i=1; 7 while(A[i-1]<A[i]) i++; 89 int pre=binary_search(A,0,i,target);10 int pos=binary_search(A,i,n-i,target);11 return pre==-1?pos:pre;12}13 private:14int binary_search(int *B,int lo,int len,int goal)15{16 int low=lo;17 int high=lo+len-1;18 while(low<=high)19 {20 int middle=(low+high)/2;21 if(goal==B[middle])//找到，返回index22return middle;23 else if(B[middle]<goal)//在右边24low=middle+1;25 else//在左边26high=middle-1;27 }28 return -1;//没有，返回-129}30 };
二、网上开源代码：
1 class Solution { 2 public: 3int search(int A[], int n, int target) { 4 int first = 0, last = n-1; 5 while (first <= last) 6 { 7 const int mid = (first + last) / 2; 8 if (A[mid] == target) 9 return mid;10 if (A[first] <= A[mid]) 11 {12 if (A[first] <= target && target < A[mid])13last = mid-1;14 else15first = mid + 1;16 } 17 else 18 {19 if (A[mid] < target && target <= A[last])20 first = mid + 1;21 else22 last = mid-1;23 }24 }25 return -1;26}27 };
如果觉得《leetcode题解：Search in Rotated Sorted Array（旋转排序数组查找）》对你有帮助，请点赞、收藏，并留下你的观点哦！
