Binary Search

easyTests passed 2026-11-11v1.0.0

TC: O(log N)|SC: O(1)

Binary Search Original Statement (leetcode).md

1. Core Invariant / The Trick

Closed interval `[l, r]` invariant: `while l <= r`, compute `mid = l + ((r - l) >> 1)` preventing 32-bit overflow, adjust `l = mid + 1` or `r = mid - 1`.

2. Complexity Bounds & Proof

Halves search space on each iteration.

3. Minimal Idiomatic Code

def search(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[m] < target: l = m + 1
        else: r = m - 1
    return -1

4. Failure Modes & Interview Follow-ups

Pitfalls:- Overflow on `(l + r) / 2` in C++/Java when indices approach `INT_MAX`.

Follow-ups:- Lower bound / Upper bound invariants for handling duplicates (`l < r` with half-open `[l, r)`).

Personal Notes & Scratchpad (Local-First Yjs CRDT)

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

Related Invariants

Search a 2D Matrix (O(log(M * N)))

Browser Scratchpad

Console Output

Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.