题目描述：
数组 $nums$ 升序排列，数组中的值互不相同。在某个下标 $k$ 旋转，变成了 $[nums[k], …, nums[n-1], nums[0],…, nums[k-1]]$ 。给出旋转之后的数组和一个目标值 $target$ ，如果数组中存在该 $target$ ，返回他的下标，不存在返回 $-1$ 。时间复杂度限制 $O(\log n)$ 。
数据范围：
$1\le n \le 5000$
题解：
类似寻找旋转数组中的最小值。使用二分搜索，找到一个 $nums[mid]$ 之后可以得到左侧或者右侧是有序的，然后判断 $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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
int search(vector<int> &nums, int target)
{
int n = nums.size();
if (n == 1)
return nums[0] == target ? 0 : -1;
int l = 0, r = n - 1, ans = -1, mid;
while (l <= r)
{
mid = (l + r) >> 1;
if (nums[mid] == target)
{
ans = mid;
break;
}
else if (nums[mid] > nums[r])
{
if (nums[mid] > target && target >= nums[l])
r = mid - 1;
else
l = mid + 1;
}
else
{
if (nums[mid] < target && target <= nums[r])
l = mid + 1;
else
r = mid - 1;
}
}
return ans;
}
};
|
需要手动将两段的划分保持一致，要不可能会陷入死循环
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
| class Solution
{
public:
int search(vector<int> &nums, int target)
{
int n = nums.size();
if (n == 1)
return nums[0] == target ? 0 : -1;
int l = 0, r = n - 1, mid;
while (l < r)
{
mid = (l + r) >> 1;
if (nums[mid] > nums[r])
{
if (nums[mid] >= target && target >= nums[l])
r = mid;
else
l = mid + 1;
}
else
{
if (nums[mid] < target && target <= nums[r])
l = mid + 1;
else
r = mid;
}
}
if (nums[l] == target)
return l;
return -1;
}
};
|