Search in Rotated Sorted Array II (Duplicates)

Share

Same as Search in Rotated Sorted Array but the array may contain duplicates. Return true if target exists, false otherwise.

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

Solution Approach

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.
Java
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)