leetcode 81 - Search in Rotated Sorted Array II

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Constraints:

1 <= nums.length <= 5000
-104 <= nums[i] <= 10^4
nums is guaranteed to be rotated at some pivot.
-104 <= target <= 104

Follow up: This problem is the same as Search in Rotated Sorted Array, where nums may contain duplicates. Would this affect the runtime complexity? How and why?

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
class Solution {
public:
bool search(vector<int> &nums, int lo, int hi, int target) {
if (lo > hi) return false;

int mid = lo + (hi - lo) / 2;

if (nums[mid] == target)
return true;

bool left_sorted = false;
bool right_sorted = false;

if (mid - 1 >= 0 && nums[lo] < nums[mid-1])
left_sorted = true;
if (mid + 1 < nums.size() && nums[mid+1] < nums[hi])
right_sorted = true;

if (left_sorted) {
if (target >= nums[lo] && target <= nums[mid-1])
return search(nums, lo, mid-1, target);
else
return search(nums, mid+1, hi, target);
} else if (right_sorted) {
if (target >= nums[mid+1] && target <= nums[hi])
return search(nums, mid+1, hi, target);
else
return search(nums, lo, mid-1, target);
} else
return search(nums, lo, mid-1, target) || search(nums, mid+1, hi, target);
}

bool search(vector<int>& nums, int target) {
return search(nums, 0, nums.size()-1, target);
}
};

//简洁写法
class Solution {
public:
bool search(vector<int>& nums, int target) {
int i = 0, j = nums.size() - 1;

while (i <= j) {
int m = i + (j-i)/2;

if (nums[m] == target) return true;

//和第33题唯一的区别
if (nums[i] == nums[m] && nums[m] == nums[j]) {
i++;
j--;
continue;
}

bool left_sorted = nums[i] <= nums[m]; //false
if ((left_sorted && target >= nums[i] && target < nums[m]) ||
/* 1 3 */
(!left_sorted && (target < nums[m] || target > nums[j]))) {

j = m - 1;
} else {
i = m + 1;
}
}

return false;
}
};