Binary Search

1. When to reach for binary search

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

For membership alone a hash set is better: O(1) instead of O(log n). Binary search earns its place when you need something a set can’t answer, all of which require order:

• Where is the element
• What’s the next value above or below it
• Where would it go if it isn’t there
• How many values are below it, or inside a range

All four come from the same operation, finding the position where the answer flips.

2. The convention

Every off-by-one bug comes from mixing conventions. Pick one and never deviate.

• low starts at 0
• high starts at len(lst) - 1, the last valid index
• Both ends are valid positions in the list
• Loop while low <= high
• mid = (low + high) // 2
• Target is bigger: low = mid + 1
• Target is smaller: high = mid - 1

The sentence that generates all of it: everything from low to high inclusive is still unchecked.

That gives you <=, because a one-element window (low == high) still has something to check. And it gives you the +1 / -1, because mid was just checked and has to leave the window.

3. Excluding mid

Not tidiness. The loop hangs without it.

Floor division rounds down, so on an even window mid lands on the lower half and can equal low. Setting low = mid then assigns low to itself and nothing shrinks:

lst = [1, 3], target = 3

low=0, high=1   mid = (0+1)//2 = 0, lst[0]=1 < 3, low = mid = 0
low=0, high=1   mid = 0 again ...

The window has to strictly shrink every iteration or the loop doesn’t terminate.

4. The canonical case

# lst is sorted ascending, no duplicates.
# Return True if target is in lst, False otherwise.

def binary_search(lst, target):
    low, high = 0, len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == target:
            return True
        elif lst[mid] > target:
            high = mid - 1
        else:
            low = mid + 1
    return False


cases = [
    ([1,3,5,7,9], 5),   # True
    ([1,3,5,7,9], 4),   # False
    ([1,3,5,7,9], 1),   # True
    ([1,3,5,7,9], 9),   # True
    ([],          5),   # False
    ([5],         5),   # True
    ([5],         3),   # False
]
for lst, target in cases:
    print(binary_search(lst, target))

The empty list needs no special case. high = -1, so 0 <= -1 is false and the loop never runs.

5. Returning the index

Same code, return mid instead of return True, and return -1 instead of False.

Use -1 rather than False for the not-found case. Python treats False as 0 in numeric contexts, so a caller writing if result: would read a genuine index 0 as not-found.

6. Notes

(low + high) // 2 is fine in Python. In C++ or Java the sum can overflow, which is why low + (high - low) // 2 is the form you see in most references.

The loop beats recursion here. Binary search discards one half rather than combining both, so there’s nothing to combine on the way back up, and the loop is easier to modify when the question changes mid-interview. Recursion is for structures that are actually recursive: trees, divide-and-conquer that merges results, backtracking.

7. The boundary variants

Exact match asks “is it here.” The boundary variants ask “where is the dividing line,” and they’re the ones that show up more, since exact match is the case where a hash set would have been better anyway.

bisect_left returns the first index where the element is no longer strictly less than the target. bisect_right returns the first index where it’s no longer less than or equal to it. On a list with no copies of the target they return the same thing, the insertion point. They only diverge on ties:

index:  0  1  2  3  4
value:  1  3  3  3  5
           ^        ^
        left=1    right=4     (target 3)

So bisect_right - bisect_left counts how many copies of the target are in the list, in O(log n) with no scan.

7.1 A different convention

The window has to change, because the answer can legally be len(lst), meaning “past the end,” and that isn’t a valid index.

• high starts at len(lst), not len(lst) - 1
• Window is [low, high), right end excluded
• Loop while low < high
• Shrink with high = mid, no -1, because high is excluded anyway and mid might be the answer
• low = mid + 1 is unchanged

The invariant is different too: not “the target is somewhere in the window” but “the answer index is somewhere in the window.” Each comparison eliminates candidate positions, and whatever position survives is the answer.

Which changes how it ends. Exact match ends by crossing (low > high), meaning the window emptied and the target wasn’t there. Boundary ends by meeting (low == high), and the meeting point is the answer. There’s no not-found case, because a dividing line always exists.

7.2 The code

def bisect_left(lst, target):
    """Index of the first element >= target."""
    low, high = 0, len(lst)
    while low < high:
        mid = (low + high) // 2
        if lst[mid] < target:   # everything <= mid is ruled out
            low = mid + 1
        else:                   # mid might be the answer, keep it
            high = mid
    return low

bisect_right is one character different, < becomes <=, which makes equal elements get skipped instead of treated as candidates:

def bisect_right(lst, target):
    """Index of the first element > target."""
    low, high = 0, len(lst)
    while low < high:
        mid = (low + high) // 2
        if lst[mid] <= target:
            low = mid + 1
        else:
            high = mid
    return low

Both are shorter than exact match because there’s no == branch and no early return.

7.3 Which bisect call answers which question

The library only ships the two >= and > versions, because those are the ones whose answer always exists. “Last index ≤ target” has no answer when every element is bigger, so it needs a not-found case. The other two are one subtraction away:

Guard the subtraction. If the result is 0 before subtracting, nothing qualified and -1 will silently index the last element instead of signalling failure:

i = bisect_right(lst, target)
if i == 0:
    return None          # every element is greater than target
return lst[i - 1]

The bottom two rows are worth memorizing as a mapping rather than derived live. Trying to invent a “last index ≤ target” loop under a clock is much harder than recognising it as bisect_right - 1.

If you do want it as a single loop, the exact-match convention plus a remembered candidate works:

low, high = 0, len(lst) - 1
ans = -1
while low <= high:
    mid = (low + high) // 2
    if lst[mid] <= target:
        ans = mid           # candidate; look right for a better one
        low = mid + 1
    else:
        high = mid - 1
return ans                  # -1 if nothing qualified

That carries a third piece of state, and handles not-found explicitly instead of by guard.

7.4 Exact match from bisect_left

Since the boundary convention is the more general one, exact match can be derived from it rather than written separately:

i = bisect_left(lst, target)
found = i < len(lst) and lst[i] == target

Worth considering as the thing to memorize: one loop shape plus two lines, instead of two loop shapes to keep straight under pressure.

8. What this page doesn’t cover

Searching an answer space rather than a list, where there’s no collection at all and the thing being searched is a range of candidate answers with a monotonic condition on them. Same window shape as the boundary variants.