leetcode题解：Search in Rotated Sorted Array（旋转排序数组查找）
题目：
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.
说明：
1）已排序数组查找采用二分查找
2）关键找到临界点
实现：
一、我的代码：
1 class Solution { 2 public: 3 int 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++; 8 9 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: 14 int 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])//找到，返回index 22 return middle; 23 else if(B[middle]<goal)//在右边 24 low=middle+1; 25 else//在左边 26 high=middle-1; 27 } 28 return -1;//没有，返回-1 29 } 30 };
二、网上开源代码：
1 class Solution { 2 public: 3 int 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]) 13 last = mid-1; 14 else 15 first = mid + 1; 16 } 17 else 18 { 19 if (A[mid] < target && target <= A[last]) 20 first = mid + 1; 21 else 22 last = mid-1; 23 } 24 } 25 return -1; 26 } 27 };