Binary search in Python

How it works

Binary search halves the search range on every step by comparing the middle element to the target. It only works on a sorted sequence, and it finds (or rules out) an item in O(log n) comparisons instead of the O(n) a linear scan would take. For a million sorted items that's about 20 comparisons versus up to a million — the difference between instant and noticeably slow.

The two pointers `lo` and `hi` mark the part of the list still worth checking. Each iteration looks at the midpoint: if it's the target you're done; otherwise you discard the half that can't possibly contain it by moving `lo` up or `hi` down. The loop ends when the pointers cross, which means the range is empty and the target isn't present, so the function returns -1.

Computing `mid` as `(lo + hi) // 2` is safe in Python because its integers grow arbitrarily large and never overflow. In fixed-width languages like Java or C, that same addition can overflow for very large indices, which is why you'll often see the defensive `lo + (hi - lo) // 2` instead. Knowing why that form exists is a common interview follow-up.

The single most important precondition is that the input is sorted. Binary search on unsorted data doesn't error — it just returns wrong answers, which makes the bug hard to spot. If your data changes often, keep it sorted on insert, or reach for a different structure such as a hash set when you only need membership tests rather than ordering.

Variations

def binary_search(items, target, lo=0, hi=None):
    if hi is None:
        hi = len(items) - 1
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if items[mid] == target:
        return mid
    if items[mid] < target:
        return binary_search(items, target, mid + 1, hi)
    return binary_search(items, target, lo, mid - 1)

from bisect import bisect_left

def index_of(items, target):
    i = bisect_left(items, target)
    if i < len(items) and items[i] == target:
        return i
    return -1

Finding an insertion point

Binary search isn't only for membership — its real power is locating where a value belongs. That's how you keep a list sorted as you insert, or find the first element greater than some threshold in a sorted log of timestamps.

from bisect import insort

scores = [40, 55, 70, 88]
insort(scores, 63)          # binary-search the slot, then insert
print(scores)               # [40, 55, 63, 70, 88]

Common mistakes & good to know

• ⚠The list must be sorted. Running binary search on unsorted data returns wrong answers silently — sort first, or use a hash set for plain membership.
• ⚠The loop condition is `while lo <= hi`, not `<`. Dropping the equals skips the case where the range has narrowed to a single element.
• ⚠If duplicates exist, this returns *some* matching index, not the first. Use bisect_left when you need the leftmost occurrence.
• ⚠Re-sorting on every search is O(n log n) and defeats the point. Sort once and keep it sorted.

Frequently asked questions