81 Search in Rotated Sorted Array II

1. Question

Follow up for "Search in Rotated Sorted Array": What ifduplicatesare allowed?
Would this affect the run-time complexity? How and why?
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).
Write a function to determine if a given target is in the array.
The array may contain duplicates.

2. Implementation

(1) Binary Search
1
class Solution {
2
public boolean search(int[] nums, int target) {
3
if (nums == null || nums.length == 0) {
4
return false;
5
}
6
7
int start = 0, end = nums.length - 1, mid = 0;
8
9
while (start + 1 < end) {
10
mid = start + (end - start) / 2;
11
12
if (nums[mid] == target) {
13
return true;
14
}
15
else if (nums[mid] < nums[end]) {
16
if (nums[mid] < target && target <= nums[end]) {
17
start = mid + 1;
18
}
19
else {
20
end = mid - 1;
21
}
22
}
23
else if (nums[mid] > nums[end]) {
24
if (nums[start] <= target && target < nums[mid]) {
25
end = mid - 1;
26
}
27
else {
28
start = mid + 1;
29
}
30
}
31
else {
32
--end;
33
}
34
}
35
36
return nums[start] == target || nums[end] == target;
37
}
38
}
Copied!

3. Time & Space Complexity

时间复杂度O(logn),空间复杂度O(1)