Binary Search

1. Why a Recipe Matters

Binary search is unusually easy to almost get right. One reusable recipe leaves more attention for the problem-specific predicate and return value.

2. The Transition-Point Recipe

Reframe the search space as two monotonic regions:

before  before  before  before | after  after  after
                                ^
                          transition point

Define is_before(x) so every “before” candidate comes before every “after” candidate. The values themselves do not need to be booleans; only this classification must be monotonic.

Recipe 1

Find the boundary between “before” and “after”

Example: target = 13, so is_before(i) = nums[i] < 13.

i=0

2

before

i=1

4

before

i=2

7

before

i=3

11

left

i=4

15

right

i=5

19

after

i=6

23

after

is_before(i) = True

is_before(i) = False

1. Establish the invariant

left is known before; right is known after.

2. Shrink the unknown gap

Move exactly one endpoint to mid without breaking the invariant.

3. Stop when adjacent

left is the last before; right is the first after.

transition_point_recipe(first, last, is_before):
    handle an empty range

    left, right = first, last
    handle left already being "after"    # the whole range is after
    handle right still being "before"    # the whole range is before

    while right - left > 1:
        mid = left + (right - left) // 2
        if is_before(mid):
            left = mid
        else:
            right = mid

    # left  = last "before"
    # right = first "after"
    return whichever boundary the problem asks for

The loop never changes:

• left remains known “before,” and right remains known “after.”
• mid is strictly between them, so every iteration makes progress.
• When they are adjacent, left and right identify the transition.

For classic search, use is_before(i) = nums[i] < target. Then right is the first value >= target; check it for equality. For an upper bound, use nums[i] <= target instead.

3. Practice the Recipe on Real Problems

For each problem, first state the “before” region, the “after” region, and whether the answer comes from left, right, or a final validation. Rotated arrays, valley bottoms, and overtaking points change those choices—not the loop.

4. Reusable Idea: Grid Flattening

If an R x C grid is sorted in complete row-major order, imagine it as one virtual sorted array of length R * C. Do not allocate that array; translate indices only when reading a cell:

• Grid to virtual index: i = r * C + c.
• Virtual index to grid: r = i // C, c = i % C.

Reusable idea

Treat an R × C grid as one array

0

1

3

4

6

7

9

11

12

13

21

31

grid[1][2] = 9

i=0

0

i=1

1

i=2

3

i=3

4

i=4

6

i=5

7

i=6

9

i=7

11

i=8

12

i=9

13

i=10

21

i=11

31

i = 1 × 4 + 2 = 6

Grid → virtual index

i = r * C + c

Virtual index → grid

(r, c) = (i // C, i % C)

This produces an $O(log(RC))$ search with $O(1)$ extra space. It is valid only when each row is sorted and the last value of one row is smaller than the first value of the next row.

5. Reusable Idea: Exponential Search and Guess-and-Check

When a search range has no known upper bound, probe 1, 2, 4, 8, ... until the predicate changes. The last two probes bracket the transition; then apply the normal recipe inside that interval.

Reusable idea

Double until the transition is bracketed

1

before

2

before

4

before

8

before

16

after

The unknown transition is now inside (8, 16].

Run the normal transition-point recipe only inside that bracket.

1. Guess

Probe 1, 2, 4, 8, ....

2. Check

Stop when the predicate changes state.

3. Refine

Binary search between the last two probes.

left, right = 0, 1
while is_before(right):
    left = right
    right *= 2

# The transition is now in (left, right].
run transition_point_recipe(left, right, is_before)

This pairs naturally with guess-and-check:

1. Guess a candidate answer.
2. Check whether it is too small, too large, feasible, or infeasible.
3. Prove those answers form one monotonic transition.
4. Binary search for the first or last candidate that satisfies the constraint.

Use this when checking one candidate is much easier than constructing the optimum directly. If the answer bounds are unknown, exponential search can discover them first.

6. Conclusion

The central idea is simple: every binary-search solution can be reframed as finding a transition point. Keep one trusted recipe and spend your problem-solving effort on three questions:

1. What is the ordered search space?
2. What does is_before(x) mean, and why is it monotonic?
3. Does the problem need the last “before,” the first “after,” or a value derived from one?

Two useful extensions cover many less-obvious cases: flatten a globally sorted grid into virtual indices, and use repeated doubling when a search bound is unknown. With those tools, binary search becomes a reusable building block instead of a collection of fragile special cases.