Same as Search in Rotated Sorted Array but the array may contain duplicates. Return true if target exists, false otherwise.
Input: nums=[2,5,6,0,0,1,2], target=0 → Output: trueInput: nums=[2,5,6,0,0,1,2], target=3 → Output: false
Same approach as version I but when nums[lo]==nums[mid]==nums[hi] we cannot determine which half is sorted, so increment lo and decrement hi.
- If nums[mid]==target return true.
- If nums[lo]==nums[mid] and nums[mid]==nums[hi]: lo++, hi-- (reduce ambiguity).
- Else if left half sorted: check if target in left, adjust lo/hi.
- Else right half sorted: check if target in right, adjust lo/hi.
class Solution {
public boolean search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return true;
if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) { lo++; hi--; }
else if (nums[lo] <= nums[mid]) {
if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return false;
}
}
- Time Complexity: O(N) worst, O(log N) average
- Space Complexity: O(1)