问题描述
给定一个包含重复元素的旋转升序数组，要求用 O(log n) 的时间复杂度查找某个元素是否在数组中。题目链接：**点我**
样例输入输出
输入：[4,5,6,7,0,1,2] 0
输出：true
输入：[4,5,6,7,0,1,2] 9
输出：false
问题解法
要求在 O(log n) 的时间复杂度查找某个元素是否在数组中，很明显需要用二分查找。当前数组是剔除了重复元素，就是一个简单旋转升序数组中查找元素的解法。代码如下
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| class Solution {
public boolean search(int[] nums, int target)
{
int start = 0;
int end = nums.length - 1;
while (start <= end)
{
int middle = (start + end) / 2;
if (nums[middle] == target || nums[start] == target || nums[end] == target)
{
return true;
}
if (end > middle && nums[end] == nums[end - 1])
{
while (end > middle && nums[end] == nums[end - 1])
{
end--;
}
end--;
continue;
}
if (start < middle && nums[start] == nums[start + 1])
{
while (start < middle && nums[start] == nums[start + 1])
{
start++;
}
start++;
continue;
}
if (nums[start] == nums[end] && start < end)
{
while (nums[start] == nums[end] && start < end)
{
start++;
end--;
}
continue;
}
if (nums[middle] < target)
{
if (nums[end] < target)
{
end = middle - 1;
}
else
{
start = middle + 1;
}
}
else
{
if (nums[start] < target)
{
end = middle - 1;
}
else
{
start = middle + 1;
}
}
}
return false;
}
}
|