Binary Search

Let us play a quick game. I am thinking of a number between 1 and 100, and after each guess I will tell you only “higher” or “lower.”

A patient player who starts at 1 and counts up might need a hundred guesses. A smart player guesses 50. If I say “higher,” they guess 75; if “lower,” 25. Each guess throws away half of what is left, and so they corner my number in about seven tries instead of a hundred. That halving is the whole idea of binary search.

The same move is what you do in a phone book. To find “Smith,” you do not start at page one — you open near the back, see “Taylor,” and know to step left. You never read every page. But notice the quiet condition that makes “step left” mean anything: the names are sorted. Without an order, “higher” and “lower” are empty words, and binary search has nothing to stand on.

Watching the range shrink

Let us search this sorted list of fifteen numbers for 23:

[3, 7, 11, 15, 19, 23, 28, 34, 40, 47, 55, 63, 72, 81, 90]

We keep two markers, lo and hi, for the part of the list still in play, and we always look at the middle of that part. Each look does one of three things: matches, sends us right, or sends us left — and either way, half the list is gone.

lo=0  hi=14   mid=7  → a[7]=34,  34 > 23, go left    → hi=6
lo=0  hi=6    mid=3  → a[3]=15,  15 < 23, go right   → lo=4
lo=4  hi=6    mid=5  → a[5]=23,  found at index 5

Three comparisons. A linear scan would have taken six to reach index 5 — and the gap only widens as the list grows.

The implementation

The code keeps exactly those two markers and that one middle look:

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid           # found it
        elif arr[mid] < target:
            lo = mid + 1         # answer is in the right half
        else:
            hi = mid - 1         # answer is in the left half
    return -1                    # lo passed hi — not here

data = [3, 7, 11, 15, 19, 23, 28, 34, 40, 47, 55, 63, 72, 81, 90]
print(binary_search(data, 23))   # the index of 23
print(binary_search(data, 50))   # 50 is not in the list

5
-1

Why “halve every step” means O(log n)

Each comparison throws away half of what remains. Starting from n items:

The search ends when one element is left, that is when n / 2ᵏ = 1, which rearranges to k = log₂ n. So the number of comparisons is the number of times you can halve n before reaching 1 — and that count is the logarithm. For a million items it is at most about twenty; a linear scan could need all 1,000,000.

The break-even comes early. Even on a sorted list of 100 items, binary search needs at most 7 comparisons against linear search’s 100. Once you search the same sorted data more than a handful of times, binary search has already paid for the sorting.

Don’t write it by hand — bisect

Python’s standard library ships a tested binary search in the bisect module, so in real code you reach for that rather than re-deriving the loop:

import bisect

data = [3, 7, 11, 15, 19, 23, 28, 34, 40, 47, 55, 63, 72, 81, 90]
print(bisect.bisect_left(data, 34))   # where 34 sits (or would sit)

7

bisect_left and bisect_right return the position where a value belongs in a sorted list. That makes them perfect for two everyday jobs beyond plain lookup:

• Sorted inserts. bisect.insort(my_list, value) keeps a list in order as you add to it — it finds the spot in O(log n).
• Range queries. bisect_left(arr, lo) and bisect_right(arr, hi) hand you the slice boundaries for every value in [lo, hi], with no scan.

And there is a deeper pattern hiding here. You do not always need an array of candidates to binary-search — you can binary-search an answer as long as the test “is this answer good enough?” only ever flips from no to yes as the value grows. That idea, binary search on the answer, is the whole of the next lesson.

Practice