Binary Search Explained Visually (and Its Off-By-One Traps)

Almost everyone can describe binary search. Far fewer can write one that is correct on the first try, and that gap is exactly what the question is for. The idea takes a sentence; the boundaries take care.

The problem it solves

You have a sorted array and you want to know whether a value is in it, and where.

Scanning left to right works and costs one look per element. On ten values nobody cares. On ten million, in a loop that runs per request, it is the difference between a service that answers and one that falls over.

Sorted order is extra information, and a linear scan throws all of it away. Binary search is what using it looks like.

The intuition

Look at the middle element. Three things can happen, and each one is a decision you never have to revisit:

• it is the target — done;
• it is smaller than the target — then so is everything to its left, because the array is sorted, so the whole left half is gone;
• it is larger — the whole right half is gone.

Every probe eliminates half of whatever is left. That is the only claim in the algorithm, and the running time falls straight out of it: the number of times you can halve n before one element remains is log₂ n.

A thousand values take about ten probes. A million take about twenty. A billion take about thirty. The reason O(log n) feels magical is that it barely moves when the input explodes.

Watch it run

Coral marks the element being probed; the greyed-out region is what the probe just eliminated. Watch the ruled-out half rather than the probe — the discarding is the algorithm.

Notice that the window never grows and never re-tests a value it has already ruled out. If either of those happens in your own code, you have a bug, and usually the same bug: a boundary that failed to move.

The code

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1          # hi is INCLUSIVE
    while lo <= hi:                    # so an empty range is lo > hi
        mid = lo + (hi - lo) // 2      # no overflow, same value as (lo+hi)//2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1               # mid is ruled out, so +1
        else:
            hi = mid - 1               # mid is ruled out, so -1
    return -1

values = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(values, 23))   # 5
print(binary_search(values, 3))    # -1

Four decisions in that function are load-bearing, and they all agree with each other: hi is inclusive, so the loop uses <=, so an exhausted range is lo > hi, so both branches step past mid. Change one and you must change the rest.

The variant that gets asked more often

"Find the target" is the warm-up. "Find the first position where the target could go" is the question behind duplicates, insert positions and most range queries — and it is a different loop.

def lower_bound(nums, target):
    lo, hi = 0, len(nums)              # hi is EXCLUSIVE this time
    while lo < hi:                     # so the empty range is lo == hi
        mid = lo + (hi - lo) // 2
        if nums[mid] < target:
            lo = mid + 1               # mid is too small: rule it out
        else:
            hi = mid                   # mid might BE the answer: keep it
    return lo                          # first index with nums[i] >= target

print(lower_bound([1, 3, 3, 3, 7], 3))   # 1
print(lower_bound([1, 3, 3, 3, 7], 4))   # 4
print(lower_bound([1, 3, 3, 3, 7], 9))   # 5

There is no equality test at all. The loop narrows until one position is left, and that position is the answer even when the target is absent — which is why it can return len(nums), a valid insertion point rather than an error.

Where it goes wrong

• hi = mid with an inclusive convention. If mid equals lo, the range never shrinks and the loop spins forever. This is the classic hang.
• mid = (lo + hi) // 2. Fine in Python, where integers are unbounded. In a fixed-width language that sum overflows on large arrays, which is the bug famously found in a standard library years after it shipped. lo + (hi - lo) // 2 costs nothing and is habit-forming.
• An unsorted input. Binary search does not detect this; it returns a confident wrong answer. If sorting is your job first, say so — O(n log n) to sort then O(log n) to search only pays off across many searches.
• Duplicates with the plain version. It returns some matching index, not the first or the last. If the question says "first", you need lower_bound.
• Floating-point ranges. When you are searching an answer space rather than an array, lo and hi are real numbers and lo < hi may never become false. Loop a fixed number of iterations — a hundred halvings is far beyond double precision — or stop on a tolerance.

How to say it in an interview

State the invariant first. It is the thing being tested:

"I keep a half-open window [lo, hi) that is the only range the answer can be in. Each probe compares the midpoint and discards the half that cannot contain it, so the window halves every iteration — that is O(log n) time and O(1) space. I use the exclusive-high form so hi = mid keeps a candidate alive, which makes the same loop return the first valid position when there are duplicates. It assumes the array is sorted; if it is not, sorting first costs O(n log n), which only pays off across repeated searches."

Then write it. Say the boundary rule out loud as you type each branch — "mid is ruled out here, so lo = mid + 1". Interviewers are listening for exactly that.