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.
思路：二分搜索，每次去掉一半的错误选项。
注意，每次 l = m + 1, r = m - 1 防止无限循环。
int search(int A[], int n, int target) {
int l = , r = n - ;
while(l <= r) //注意有等号
{
int m = (l + r) / ;
if(A[m] == target)
return m;
if(A[l] <= A[m] && A[m] <= A[r]) //顺序的
{
if(A[m] > target)
r = m - ;
else
l = m + ;
}
else if(A[l] >= A[m] && A[m] <= A[r]) //开头转到了左半部分
{
if(A[m] < target && target <= A[r]) //在右半部分
l = m + ;
else
r = m - ;
}
else //开头转到了右半部分
{
if(A[l] <= target && target <= A[m]) //在左半部分
r = m - ;
else
l = m + ;
}
}
return -;
}
大神简约版写法：去掉一半选项时的思路不同
int search(int A[], int n,int target) {
int lo = ;
int hi = n - ;
while (lo <= hi) {
int mid = (lo + hi) / ;
if (A[mid] == target) return mid;
if (A[lo] <= A[mid]) {
if (target >= A[lo] && target < A[mid]) {
hi = mid - ;
} else {
lo = mid + ;
}
} else {
if (target > A[mid] && target <= A[hi]) {
lo = mid + ;
} else {
hi = mid - ;
}
}
}
return -;
}