Binary Search Pattern: Invariant, Example & Boundaries

What is binary search really doing?

Binary search maintains a range of candidates and uses a middle test to prove that one half is impossible. In a sorted array, if values[mid] is smaller than the target, every value at or left of mid is also too small. The remaining answer must be to the right.

The pattern is broader than “find this number in a sorted array.” It applies whenever a search space has a monotonic boundary: false then true, infeasible then feasible, too small then large enough.

Invariant

At the start of each loop, the answer—if it exists—is inside the active search range. Every boundary update preserves that statement while making the range smaller.

When should you consider binary search?

Sorted data

The ordering lets a comparison rule out every value on one side of the middle.

Monotonic condition

A predicate switches only once, such as “capacity is sufficient” after a threshold.

Minimize the maximum

You can ask whether a proposed answer is feasible, then search for the smallest feasible value.

Huge numeric range

Testing an answer is affordable, but checking every possible value would be too slow.

Sorted input is necessary for the classic value search, but not every sorted problem needs binary search. Use it only when the middle comparison safely eliminates a full side.

Step-by-step: find 13

Search for 13 in [2, 5, 8, 12, 13, 17].

Interactive middle trace

258121317

Compare the middle value to the target.

Middle index 2 holds 8, which is too small. Move left to 3.
New middle index 4 holds 13. Return index 4.

Notice the update left = mid + 1. Index mid has already been tested and disproved; keeping it in the range can cause an infinite loop.

Classic exact-search outline

left = 0
right = values.length - 1

while left <= right:
    mid = left + (right - left) / 2

    if values[mid] == target:
        return mid
    else if values[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

return not found

This is a closed interval: both left and right are candidates, which is why the loop uses left <= right. Other valid templates use a half-open interval. Choose one contract and keep its loop condition, middle calculation, updates, and return value consistent.

Why is binary search O(log n)?

The number of candidates follows n, n/2, n/4, n/8…. After k rounds, about n / 2^k candidates remain. The search ends when that value reaches 1, so k grows like log₂ n. Iterative binary search uses O(log n) time and O(1) extra space.

Binary search on the answer

Suppose the answer is not stored in an array, but you can test whether a candidate value is sufficient. If every value below some threshold fails and every value at or above it succeeds, search that numeric range.

left = smallest possible answer
right = largest possible answer

while left < right:
    mid = left + (right - left) / 2
    if feasible(mid):
        right = mid
    else:
        left = mid + 1

return left  // first feasible answer

The essential proof is monotonicity. Once feasible(x) becomes true, it must stay true for all larger candidates—or the half-space elimination is not safe.

Common binary search mistakes

Mixing interval contracts: a closed interval and a half-open interval use different conditions and updates.
Keeping mid accidentally: exact search updates normally use mid + 1 or mid - 1.
Returning the last middle by habit: boundary searches often return left after convergence.
Skipping the monotonicity proof: answer-space search is invalid if feasibility can flip back and forth.
Off-by-one tests: always test an empty input, one item, two items, missing targets, and both endpoints.

Interview explanation

“My invariant is that every remaining candidate lies inside this interval. The middle test proves one side is impossible, so the interval shrinks by roughly half each round.”

Continue learning

Two pointers

Use sorted order to choose one boundary move at a time.

COMPARE →Big-O analysis

Read halving as a logarithmic cost story.

ANALYZE →

Make the boundary concrete

Practice binary search visually on iPhone.

Learn exact search, answer-space search, solution outlines, edge cases, and Big-O tradeoffs.

Binary search: order makes elimination safe.