题目描述：
数组 $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$ 是否在该有序的区间内部，根据这个进行二分。主要是排除解肯定不在的区间。如果遇到 $nums[mid] = nums[r]$ 则可以将 $r$ 排除掉，直接 $r = r - 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
31
32
33
34
35
36
37
38
39
40
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
bool search(vector<int> &nums, int target)
{
int n = nums.size();
int l = 0, r = n - 1, mid, ans = -1;
while (l <= r)
{
mid = l + r >> 1;
if (nums[mid] == target)
{
ans = mid;
break;
}
else if (nums[mid] > nums[r])
{
if (nums[l] <= target && target < nums[mid])
r = mid - 1;
else
l = mid + 1;
}
else if (nums[mid] < nums[r])
{
if (nums[mid] < target && target <= nums[r])
l = mid + 1;
else
r = mid - 1;
}
else if (nums[mid] == nums[r])
{
r--;
}
}
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
34
35
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
bool search(vector<int> &nums, int target)
{
int n = nums.size();
int l = 0, r = n - 1, mid, ans = -1;
while (l < r)
{
mid = (l + r) >> 1;
if (nums[mid] > nums[r])
{
if (nums[l] <= target && target <= nums[mid])
r = mid;
else
l = mid + 1;
}
else if (nums[mid] < nums[r])
{
if (nums[mid] < target && target <= nums[r])
l = mid + 1;
else
r = mid;
}
else if (nums[mid] == nums[r])
{
r--;
}
}
return nums[l] == target;
}
};
|