What is the most efficient way to find a number in a sorted array of one billion entries? It depends on what you mean by "efficient", but if the array fits in memory and you can read any index in O(1), the answer is binary search and it finishes in roughly 30 comparisons. Thirty. Out of a billion. The intuition that one extra comparison doubles the search space is the closest thing computer science has to a magic trick, and once it clicks you start seeing it everywhere.

This is the version of binary search I wish someone had handed me before I memorized three different broken templates. The goal is one template, three variations that cover most problems, and a hard-won note on the off-by-one bug that is the single most common reason real binary search code is wrong.

The mental model: search the answer space

Forget arrays for a second. Binary search works whenever your problem has these three properties:

1. There is an ordered space of possible answers.
2. You have a predicate that, given a candidate answer, returns yes or no.
3. The predicate is monotonic: once it flips from no to yes (or yes to no), it never flips back.

In a sorted array [1, 3, 5, 7, 9, 11] looking for 7, the answer space is the indices [0, 5], and the predicate is "is arr[i] >= 7". The predicate is false, false, false, true, true, true. Binary search finds the boundary.

This framing is what lets you generalize. "Find the smallest server count that handles peak load" is binary search. "Find the lowest version that has the bug" is binary search (this is what git bisect does). "Find the smallest box that fits all the items" is binary search. The arrays are a special case of "search the answer space".

The template I actually use

I used to write a different binary search every time I needed one, and I got it wrong about half the time. The fix was committing to a single template that works for every variant I have hit. Here it is.

def binary_search(lo, hi, predicate):
    """
    Returns the smallest x in [lo, hi] for which predicate(x) is True.
    Assumes predicate is monotonic: once True, always True for larger x.
    Assumes such an x exists; otherwise returns hi + 1.
    """
    while lo < hi:
        mid = lo + (hi - lo) // 2     # avoids overflow in languages where it matters
        if predicate(mid):
            hi = mid                  # mid might be the answer; keep it in range
        else:
            lo = mid + 1              # mid is definitely not the answer
    return lo

The loop condition is lo < hi, not lo <= hi. The shrinking step is hi = mid (not hi = mid - 1) when the predicate succeeds. These two choices keep the answer in the range [lo, hi] and let the loop terminate cleanly. Do them differently and you either skip the answer or loop forever, and that is the source of every binary search bug.

For finding a target value in a sorted array, the predicate is arr[mid] >= target. The result is the leftmost index i such that arr[i] >= target. If arr[i] == target, you found it. If not, the target is not in the array.

Variation 1: find an exact value

The most basic case. Sorted array, find the target, return the index or -1.

def find(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] >= target:
            hi = mid
        else:
            lo = mid + 1
    if lo < len(arr) and arr[lo] == target:
        return lo
    return -1

Notice hi = len(arr), not len(arr) - 1. The range is the half-open interval [lo, hi), which is the convention I find easiest to reason about. The valid answers are indices 0 through len(arr) - 1, plus the sentinel "past the end" position len(arr) for "target is greater than every element".

Variation 2: leftmost / rightmost occurrence in a sorted array with duplicates

When the array has duplicates and you want the first or last occurrence, the predicate changes.

def leftmost(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] >= target:    # leftmost: shrink right when we see target
            hi = mid
        else:
            lo = mid + 1
    return lo

def rightmost(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] > target:     # rightmost: shrink right only when strictly greater
            hi = mid
        else:
            lo = mid + 1
    return lo - 1                 # one past the last occurrence, then back up

The one character difference between >= and > is the entire trick. Knowing which one to write requires you to remember what the loop is computing: the leftmost index where the predicate is true. If the predicate is >=, that is the first occurrence. If the predicate is >, that is the position after the last occurrence.

Variation 3: binary-search the answer (not an index)

This is the one that took me years to recognize. Many problems are not "find an index in a sorted array" but "find the smallest value that satisfies a property". The classic example:

# You have packages with weights[]. Ship them in `days` days.
# Each day's load must fit in the ship's capacity.
# What's the minimum capacity?

def min_capacity(weights, days):
    def can_ship(capacity):
        used_days = 1
        load = 0
        for w in weights:
            if w > capacity:
                return False         # one package alone exceeds capacity
            if load + w > capacity:
                used_days += 1
                load = 0
            load += w
        return used_days <= days

    lo = max(weights)               # capacity must hold the heaviest package
    hi = sum(weights)               # capacity of `sum` always works in 1 day
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_ship(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

The answer space here is integer capacities from max(weights) to sum(weights). The predicate can_ship(capacity) is monotonic: once a capacity is large enough to ship in days days, every larger capacity also works. Same template, different domain. The shape of the loop is identical to Variation 1.

ASCII walkthrough: a concrete trace

Let me trace find([2, 5, 8, 11, 14, 17, 20], 14) step by step.

start:   lo=0, hi=7,  range=[2,5,8,11,14,17,20]
         mid=3, arr[3]=11, 11<14, so lo=4

step 2:  lo=4, hi=7,  range=[14,17,20]
         mid=5, arr[5]=17, 17>=14, so hi=5

step 3:  lo=4, hi=5,  range=[14,17]
         mid=4, arr[4]=14, 14>=14, so hi=4

step 4:  lo=4, hi=4,  loop exits.
         arr[4]=14 == 14, return 4.

Three comparisons to find the target in an array of seven. The pattern scales: ten comparisons covers a thousand items, twenty covers a million, thirty covers a billion. This is what O(log n) feels like.

The off-by-one bug everyone writes

The canonical broken version is some flavor of this:

def broken(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

It looks reasonable. It even works for finding an exact value. But mix conventions (hi = len(arr) - 1 here, vs hi = len(arr) in my template) and start adapting the code for "leftmost" or "rightmost" or "answer space", and you will eventually write the variant that loops forever or skips the boundary. The fix is to commit to one convention and never deviate. I use [lo, hi) (half-open), lo < hi loop, hi = mid shrink. Every binary search I write looks the same. Every binary search I write is correct on the first try, mostly because the template has been debugged once and I do not redebug it.

Default to one template. Vary only the predicate.

The single most useful thing I can hand a junior engineer about binary search is: pick one template and never write another. The variations between problems live in the predicate, not the loop. Once your loop is correct, the only question is what predicate(mid) returns, and that is a function of the problem domain. Leftmost vs rightmost? Change >= to >. Find the smallest capacity? Write a can_ship predicate. git bisect-style? The predicate is "is this commit broken". Same loop, different domain. Try this on three or four binary-search problems in a row using the template above and you will stop misremembering the boundary conditions, because there is only one set of boundary conditions to remember. The cost is committing to a convention. The benefit is shipping correct binary search every time.