思路
最开始想的是先通过二分来找到最大值位置，确定$right$和$left$的值，再使用一次二分来进行查询。但仔细观察题目发现只需进行一次二分查找算法就可以解决问题了，因为 「该旋转后的数组从中间分开后，左右部分中必定有一个部分是有序的」。
那么我们就可以借助这个有序数组来直接进行二分查找，采用下面的方式来更新$left$和$right$的值：
- 左边部分有序
- target在这个有序区间内，则可以直接抛弃右边部分。反之，抛弃左边部分。
- 右边部分有序
- target在这个有序区间内，则可以直接抛弃左边部分。反之，抛弃右边部分。
代码
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
class Solution
{
public:
int search(vector<int>& nums, int target)
{
int mid, left = 0;
int right = nums.size() - 1;
while (left <= right)
{
mid = ((right - left) >> 1) + left;
if (target == nums[mid])
{
return mid;
}
// 判断左边是否有序, 这里是 <= 是为了处理左边只有一个元素的情况
if (nums[left] <= nums[mid])
{
// 左边有序
if (nums[left] <= target && nums[mid] > target)
{
// 在区间内
right = mid - 1;
}
else
{
left = mid + 1;
}
}
else
{
// 右边有序
if (nums[mid] < target && target <= nums[right])
{
// 在区间内
left = mid + 1;
}
else
{
right = mid - 1;
}
}
}
return -1;
}
};
|
zyz