81. Search in Rotated Sorted Array II
1. Description
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.
2. Example
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
3. Constraints
- 1 <= nums.length <= 5000
- $-10^4$ <= nums[i] <= $10^4$
- nums is guaranteed to be rotated at some pivot.
- $-10^4$ <= target <= $10^4$
4. 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?
5. Solutions
My Accepted Solution
n = i_nums.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
bool search(const vector<int>& i_nums, int target) {
for (int left = 0, right = i_nums.size() - 1; left <= right;) {
int middle = left + (right - left) / 2;
if (i_nums[middle] == target) {
return true;
}
if (i_nums[left] < i_nums[right]) {
return binary_search(i_nums.begin() + left, i_nums.begin() + right + 1, target);
} else if (i_nums[left] == i_nums[middle]) {
++left;
} else {
bool pivotArray = i_nums[left] <= i_nums[middle];
bool targetArray = i_nums[left] <= target;
if (pivotArray ^ targetArray) { // pivot and target exist in different parts
if (pivotArray) { // pivot in the first, target in the second
left = middle + 1;
} else { // target in the first, pivot in the second
right = middle - 1;
}
} else { // If pivot and target exist in same sorted array
if (i_nums[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
}
}
return false;
}
};