source: https://leetcode.com/problems/search-in-rotated-sorted-array
C/C++ Solution to LeetCode problem 81. Search in Rotated Sorted Array II.
Problem
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
.
You must decrease the overall operation steps as much as possible.
Examples
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] <= 104
nums
is guaranteed to be rotated at some pivot.-104 <= target <= 104
Solution
Solution is same as in problem #33, the only difference is that numbers can be repeated so:
- While lower index
<
higher index:- While the value at the lower index is equal to the next one, move the lower index up.
- While the value at the higher index is equal to the previous one, move the higher index down.
- Perform binary search as in problem #33
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
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int h = nums.size() - 1;
int m;
while (l <= h) {
while (l < h && nums[l] == nums[l+1])
l ++;
while (h > l && nums[h] == nums[h-1])
h --;
m = (l + h) / 2;
if (nums[m] == target)
return true;
if (nums[l] <= nums[m]) {
if (target <= nums[m] && target >= nums[l])
h = m - 1;
else
l = m + 1;
} else {
if (target >= nums[m] && target <= nums[h])
l = m + 1;
else
h = m - 1;
}
}
return false;
}
};