Search in Rotated Sorted Array II

medium array binary search

Problem

Given a possibly-rotated sorted array nums that may contain duplicates and a target, decide whether target exists in nums.

Inputnums = [2, 5, 6, 0, 0, 1, 2], target = 0

Outputtrue

0 is present in the array.

nums (rotated, comma-separated)

target

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] == nums[hi]:
            lo += 1
            hi -= 1
        elif nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]: hi = mid - 1
            else: lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]: lo = mid + 1
            else: hi = mid - 1
    return False

function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] === target) return true;
    if (nums[lo] === nums[mid] && nums[mid] === nums[hi]) { lo++; hi--; }
    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;
}

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 (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;
    }
}

bool search(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 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 (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;
}

Explanation

This is binary search on a rotated array, but with a twist: duplicates are allowed. The duplicates make one case ambiguous, and handling that case is the whole challenge.

The normal rotated-array trick is that at any mid, at least one half is properly sorted. We check nums[lo] <= nums[mid] to see if the left half is sorted; if the target falls inside that sorted range we keep that half, otherwise we keep the other. The same logic mirrors for the right half.

The new wrinkle is when nums[lo] == nums[mid] == nums[hi]. Now we cannot tell which side is sorted, so we cannot safely discard half. The safe move is to shrink both ends by one with lo++ and hi-- and try again. This is what can degrade the worst case to O(n).

Example: nums = [2,5,6,0,0,1,2], target 0. At mid we find nums[mid] is not 0; the code identifies the sorted half, sees 0 is not in it, and moves toward the rotated part, eventually landing on a 0 and returning true.

On average the duplicate-collapse case is rare, so this still behaves like O(log n); only adversarial inputs full of equal values push it to linear time.

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