Search In Rotated Sorted Array II

MEDIUM✓ CHIP-TIMEDLC #81 — FULL STATEMENT ↗

The drill: Same rotated-array search as before, but duplicate values are now allowed — decide only whether the target exists, since duplicates make returning a single index ambiguous.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

This is the same rotated-array hunt as before, except duplicate values are now allowed to appear anywhere in the array, which quietly breaks some of the tricks that worked when every value was distinct.

A target value arrives with the array, and the only question worth answering is whether that value exists somewhere inside it — with duplicates around, a single matching index would be ambiguous anyway, so existence is all that's asked.

Repeated values can make the two endpoints and the midpoint of a search window all look identical, which hides which half of the window is actually the sorted one — the drill has to account for that blind spot.

EX 01

nums = [2, 3, 3, 4, 1, 1] · target = 3

→ true

DUPLICATE VALUES, HIT

EX 02

nums = [2, 3, 3, 4, 1, 1] · target = 5

→ false

DUPLICATE VALUES, ABSENT TARGET

EX 03

nums = [1, 1, 1, 1, 1, 1, 2] · target = 2

→ true

HEAVY DUPLICATES, TARGET AT THE VERY END

array holds up to a few thousand values, duplicates allowed
array may be rotated by any amount, including not at all
only a true/false existence answer is expected, no index
worst case with heavy duplication can degrade toward a full scan

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Duplicates can make nums[lo], nums[mid], and nums[hi] all equal, which breaks the trick of telling which half is sorted by comparing endpoints — what's the safe fallback when that comparison is uninformative?

HINT 2 THE STRUCTURE

When nums[lo] == nums[mid] == nums[hi], you can't tell which side is sorted — just shrink the window by one from each end and keep going; you lose at most O(1) work per collision.

HINT 3 ONE STEP FROM THE ANSWER

Otherwise, run the same sorted-half test as the distinct-values version: whichever side is strictly ordered end-to-end tells you where to look, and where to discard.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE TIE BREAKERPATTERN · MODIFIED BINARY SEARCH + SKIP TIESnums = [1, 1, 1, 1, 0, 1, 1] · target = 0

STEP 1

Target 0, and duplicates are everywhere — the usual sorted-half trick can get confused when the edges tie with the middle.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/search-in-rotated-sorted-array-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        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

TIME O(N) WORST CASE, O(LOG N) AVERAGESPACE O(1)PYTHON · RACE PACE · 21 LN

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        for v in nums:
            if v == target:
                return True
        return False

TIME O(N)SPACE O(1)PYTHON · TRAINING PACE · 6 LN

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

TIME O(N) WORST CASE, O(LOG N) AVERAGESPACE O(1)JAVA · RACE PACE · 28 LN

class Solution {
    public boolean search(int[] nums, int target) {
        for (int v : nums) {
            if (v == target) {
                return true;
            }
        }
        return false;
    }
}

TIME O(N)SPACE O(1)JAVA · TRAINING PACE · 10 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED