12
Binary Search (Modified)
Searching a sorted or monotonic answer space.
6 pages
- Pattern 12: Binary Search (Modified)Pattern guide
Three skeletons. Template B (find the boundary) is the one to memorise — it solves far more interview problems than the exact-match version, and it never…
- LC 704Binary Search (LC 704)Easy
Halve the search space each step using a sorted array and a three-pointer invariant (left, right, mid).
- LC 35Search Insert Position (LC 35)Easy
When the search interval empties, left is the first index where you could insert target while keeping order.
- LC 34Find First and Last Position of Element in Sorted Array (LC 34)Medium
Run two separate binary searches: one for the first index with value target, one for the last.
- LC 74Search a 2D Matrix (LC 74)Medium
Rows sorted + last of row < first of next row ⇒ the whole matrix is sorted in row-major order; map flat index mid to (row, col).
- LC 278First Bad Version (LC 278)Easy
Monotone predicate: versions 1..k are good, k+1..n are bad; binary search for the smallest bad version.