题目链接:Search in Rotated Sorted Array II
Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
这道题的要求是在Search in Rotated Sorted Array的基础上允许数组中出现重复元素。
这道题是Search in Rotated Sorted Array的扩展,允许数组中出现重复元素。
思路类似,只不过当A[l] == A[m]的时候,无法判断左侧是否旋转,因此需要遍历l到m之间的元素进行查找,这样,最差的时间复杂度为O(n)。
时间复杂度: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
30
31
32
33
34
35
36
37
class Solution
{
public:
bool 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 true;
if(A[l] == A[m])
{
for(int i = l; i < m; ++ i)
if(A[i] == target)
return true;
l = m + 1;
}
else 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 false;
}
};