LeetCode 704 – Binary Search
Given sorted array + target → return index or -1.
Maintain [lo, hi] (inclusive) or [lo, hi) (half-open) invariant.
Loop: mid = lo + (hi-lo)/2; compare and shrink to the half that can contain target.
Stop when range empty; verify.
Time O(log n), Space O(1).
Tags: Binary Search template, Invariants.
LeetCode 74 – Search a 2D Matrix
Rows sorted; first of each row > last of previous row; search target.
Treat matrix as flattened sorted array of size m*n.
Binary search over [0, m*n); map idx → (idx/n, idx%n).
Time O(log(mn)), Space O(1).
(Alt: binary search row, then within row.)
Tags: Binary Search on index mapping.
LeetCode 875 – Koko Eating Bananas
Min integer speed k to eat all piles within h hours.
Binary search on answer k in [1, max(pile)].
Feasibility: hours needed = sum(ceil(p/k)) ≤ h ?
If feasible → search left; else → right.
Time O(n log maxPile).
Tags: BS on answer, Feasibility check.
LeetCode 153 – Find Min in Rotated Sorted Array (no dups)
Compare nums[mid] with nums[hi]:
If mid > hi → min in right half (lo = mid+1).
Else → min in left incl. mid (hi = mid).
End at lo == hi → nums[lo].
Time O(log n).
Tags: Rotated array, Right-biased BS.
LeetCode 33 – Search in Rotated Sorted Array
Find target; array rotated, no duplicates.
At each step one half is sorted.
If nums[lo] ≤ nums[mid] (left sorted): check if target in [lo, mid].
If yes, hi = mid-1; else lo = mid+1.
Else (right sorted): check [mid, hi] similarly.
Time O(log n).
Tags: Rotated BS, Half identification.
LeetCode 981 – Time Based Key-Value Store
set(key, value, timestamp); get(key, timestamp) → value with greatest ts ≤ timestamp.
For each key, store sorted list of (timestamp, value).
get: binary search by timestamp to find rightmost ≤ t.
set: append (timestamps strictly increasing per key).
Time: set O(1), get O(log n).
Tags: BS on timestamps, Per-key arrays.
LeetCode 4 – Median of Two Sorted Arrays
Two sorted arrays; find median in O(log(m+n)).
Binary search partition on the smaller array.
Choose i in A, j = half - i in B s.t. A[i-1] ≤ B[j] and B[j-1] ≤ A[i].
Median = average/max of the borders depending on parity.
Handle edges with ±∞ sentinels.
Time O(log min(m,n)), Space O(1).
Tags: BS on partition, Array math.
