题目链接：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.
这道题的要求是在一个经过旋转的有序数组中，找到给定的target，返回其索引。如果不存在，返回-1。可以假设数组中没有重复元素。
直接思路，遍历数组，是将复杂度O(n)。但由于数组有序，可以考虑二分查找，不过由于数组经过旋转，而且不知道在何处为旋转点，因此会比普通的二分查找多了一些判断条件：
- 当target大于A[m]时，如果target存在，则应该在m的右侧或者因为旋转而转到m的左侧。先考虑因为旋转而转到m的左侧的情形，这需要满足两个条件：m右侧没有旋转（即A[m]小于A[r]）和target大于A[r]，这时便可以确定target在m的左侧了，可令r等于m-1。而其他情况，target就在m的右侧。
- 当target小于A[m]时，如果target存在，则应该在m的左侧或者因为旋转而转到m的右侧。先考虑因为旋转而转到m的右侧的情形，这需要满足两个条件：m左侧没有旋转（即A[m]大于A[r]）和target小于A[l]，这时便可以确定target在m的右侧了，可令l等于m+1。而其他情况，target就在m的右侧。
时间复杂度：O(logn)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
public:
int search(int A[], int n, int target)
{
int l = 0, r = n - 1;
while(l <= r)
{
int m = (l + r) / 2;
if(A[m] == target)
return m;
else if(target > A[m])
{
if(A[m] < A[r] && target > A[r])
r = m - 1;
else
l = m + 1;
}
else
{
if(A[m] > A[r] && target < A[l])
l = m + 1;
else
r = m - 1;
}
}
return -1;
}
};
另一种思路：先通过比较A[l]和A[m]的大小判断左侧是否旋转。
- 如果A[l] <= A[m]，则说明左侧没有发生旋转，即左侧是递增的，因此如果target在A[l]和A[m]之间，则令r等于m-1，否则说明target在右侧，则令l等于m+1；
- 如果A[l] > A[m]，则说明右侧没有发生旋转，即右侧是递增的，因此如果target在A[m]和A[r]之间，则令l等于m+1，否则说明target在左侧，则令r等于m-1；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution
{
public:
int search(int A[], int n, int target)
{
int l = 0, r = n - 1;
while(l <= r)
{
int m = (l + r) / 2;
if(A[m] == target)
return m;
if(A[l] <= A[m])
{
if(A[l] <= target && target < A[m])
r = m - 1;
else
l = m + 1;
}
else
{
if(A[m] < target && target <= A[r])
l = m + 1;
else
r = m - 1;
}
}
return -1;
}
};