Search in Rotated Sorted Array II — Handle Duplicates

Problem 332 · Search in Rotated Sorted Array II

Difficulty: Medium · Pattern: Rotated + Duplicate Handling

Same as rotated search but nums may have duplicates.

Intuition

If nums[lo] == nums[mid], we can't determine which half is sorted → skip one element: lo++.

Solutions

# Python
def search(nums, target):
    lo, hi = 0, len(nums)-1
    while lo <= hi:
        mid = (lo+hi)//2
        if nums[mid] == target: return True
        if nums[lo] == nums[mid]:  # can't determine sorted half
            lo += 1
        elif nums[lo] <= nums[mid]:  # left sorted
            if nums[lo] <= target < nums[mid]: hi = mid-1
            else: lo = mid+1
        else:  # right sorted
            if nums[mid] < target <= nums[hi]: lo = mid+1
            else: hi = mid-1
    return False

// Java
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]) lo++;
        else if (nums[lo]<=nums[mid]) {
            if (nums[lo]<=target&&target<nums[mid]) hi=mid-1; else lo=mid+1;
        } else {
            if (nums[mid]<target&&target<=nums[hi]) lo=mid+1; else hi=mid-1;
        }
    }
    return false;
}

Complexity

Time: O(log n) average, O(n) worst case (all duplicates)
Space: O(1)