Search in Rotated Sorted Array

mediumTests passed 2026-11-11v1.0.0
TC: O(log N)|SC: O(1)
Binary SearchOriginal Statement (leetcode).md

1. Core Invariant / The Trick

At least one half (`[l..mid]` or `[mid..r]`) is guaranteed strictly sorted. Identify the sorted half via `nums[l] <= nums[mid]`, check whether `target` falls within its numeric bounds, and discard the other half.

2. Complexity Bounds & Proof

Halves search window per comparison without finding pivot in a separate pass.

3. Minimal Idiomatic Code

def searchRotated(nums: list[int], target: int) -> int:
    l, r = 0, len(nums) - 1
    while l <= r:
        m = (l + r) // 2
        if nums[m] == target: return m
        if nums[l] <= nums[m]:
            if nums[l] <= target < nums[m]: r = m - 1
            else: l = m + 1
        else:
            if nums[m] < target <= nums[r]: l = m + 1
            else: r = m - 1
    return -1

4. Failure Modes & Interview Follow-ups

Pitfalls:- Note `<=` in `nums[l] <= nums[mid]` when `l == mid` on a 2-element subarray.
Follow-ups:- Rotated Array with duplicates (`Search II`): handle `nums[l] == nums[mid] == nums[r]` by `l++; r--;`.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Find Minimum in Rotated Sorted Array (O(log N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.