Halving the search space

A sorted list provides some information with every value. If you read a value from the middle, you can infer information about the values above and below it. Binary search uses this information to make searching fast and efficient.

The problem

You have a list a of n numbers, sorted from smallest to largest, and a target value t. Find an index i where a[i] == t. If t is not in the list, return -1.

The simple way is to check each value from the left until you find t or reach the end. This is called a linear scan. In the worst case it reads all n values. It does not use the fact that the list is sorted.

The sorting gives us extra information. Say you are looking for 25, and you read a[7] = 31. The list is sorted, so every value after index 7 is bigger than 31, which means it is also bigger than 25. With one read, you have ruled out half the list.

Rule out half with each read

Keep track of the part of the list where t could still be. We call this part the window. It runs from index lo to index hi. At the start, the window is the whole list.

Then repeat these steps. Find the middle index of the window, mid, and compare a[mid] with t:

• If a[mid] == t, you have found it. Return mid.
• If a[mid] < t, then t must be to the right of mid. Every value from lo to mid is at most a[mid], so none of them can be t. Set lo = mid + 1.
• If a[mid] > t, then t must be to the left of mid, for the same reason. Set hi = mid - 1.

If the window becomes empty, t is not in the list.

Try it in the figure below. Each pointer (lo, mid and hi) moves along its own track under the list. Shaded cells have been ruled out. Also try the target that is not in the list, and watch the window shrink to nothing.

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

Line 4 finds the middle of the window. The rest of the code only moves lo and hi. The next lesson proves that these moves are correct.

How many reads it takes

Each read cuts the window at least in half. If the window has m values, the part that is left has at most m/2 values (rounded down). So after k reads, at most n / 2^k values are left. The loop stops when no values are left. This means the worst case is:

Here log₂ n means “how many times you can halve n before you reach 1”. For example, log₂ 16 = 4, because 16 → 8 → 4 → 2 → 1. The symbols ⌊ ⌋ mean “round down”.

When the list becomes 1,000 times bigger, binary search needs only about 10 more reads. This is why logarithmic time is so fast.

There is one hidden cost: the list must already be sorted. Sorting takes O(n log n) time, which is much more than one linear scan. So binary search is worth it when the data is already sorted, or when you sort it once and then search it many times. Sorting a list just to search it once is usually slower than a linear scan.

Why you cannot do better

Can any method find t with fewer reads? Not if it only compares t with values in the list.

Think of the search as a game of yes-or-no questions. There are n + 1 possible answers: t can be at any of the n positions, or it can be missing. Each question can at best cut the possible answers in half. So k questions can tell apart at most 2^k answers. To be sure of the answer, we need 2^k ≥ n + 1, which means k ≥ log₂(n + 1).

Binary search uses ⌊log₂ n⌋ + 1 reads. For every n ≥ 1, this is the same as ⌈log₂(n + 1)⌉ (where ⌈ ⌉ means “round up”), which is exactly the lower limit. So no method that only compares values can beat binary search.

In Python

Python has binary search built in, in the bisect module. bisect_left(a, t) returns the first index where t could be inserted while keeping a sorted. If t is in the list, that is where it is:

from bisect import bisect_left

def search(a, t):
    i = bisect_left(a, t)
    return i if i < len(a) and a[i] == t else -1

Two warnings. First, t in a and a.index(t) check a list one value at a time. Python does not know that your list is sorted. Second, write the loop yourself before you use bisect. The practice tests accept both, but the next five lessons build on the loop.

Next, you will prove that the loop is correct. That is the only way to be sure that the + 1 and - 1 are in the right places. The third lesson covers bisect in more detail.