Binary search

Picture a guessing game. A friend thinks of a number from 1 to 100 and answers each guess with "higher" or "lower" only. You could name the numbers in a row: 1, 2, 3… Then you might need a hundred guesses. Or you could start with 50: whatever the answer, half the numbers drop out.

A list works the same way. To find a number in it, a function can compare each element with it in turn. This scan is called linear search. In a list of a million elements, it may need a million comparisons:

def linear_search(nums, target):
    for i, x in enumerate(nums):
        if x == target:
            return i
    return -1


nums = [3, 8, 15, 21, 30, 42, 57]
print(linear_search(nums, 42))  # 5
print(linear_search(nums, 10))  # -1

Let's go through what the function does:

1. enumerate(nums) hands out pairs of an index and an element.
2. As soon as an element equals the target, the function returns its index. For 42, that is 5.
3. If the loop gets through the whole list without a match, the function returns -1. That is what happens with 10.

Halving the list

The list nums is sorted in ascending order, and that makes a faster search possible. Binary search compares the target with the middle element, the way a player names the middle number. If the middle one is less than the target, so are all elements to its left, and that half can be dropped. If it is greater, the right half is dropped.

The search keeps two bounds and a middle index:

• lo is the index of the first element where the target can still be;
• hi is the index of the last such element;
• mid is the middle index, (lo + hi) // 2.

This is how the search for 10 goes in the same list:

The middle element already checked is left out of the new bounds. Once lo is greater than hi, there is nowhere left to look, and the target is not in the list. If the middle element equals the target, the search returns its index right away.

This is where the game analogy stops. Your friend answers "higher" or "lower" honestly, while a list answers with its order. If the list is not sorted, its answers mislead, and the search drops the wrong half.

The search in a program

Here is the same search in code, for the number 30, which is in the list. Click "Next step" and watch lo, hi and mid: after each comparison, one of the bounds jumps past mid.

The loop while lo <= hi runs while at least one element is left between the bounds. At the third comparison, lo and hi are both 4, and the middle element is exactly 30. If 30 were not in the list, hi would become less than lo. The loop would end, and found would still hold -1.

How many steps it takes

Each step halves the part of the list where the target can be. A million elements can be halved about 20 times before one is left, so binary search needs about 20 comparisons.

Interviewers like to ask this: "How does binary search work, and what does it need?" A good answer has two parts:

• the search compares the target with the middle element and drops half, so a million elements take about 20 steps;
• the list must be sorted, or the target may sit in the dropped half.

The bisect module

The standard library already has binary search. The function bisect.bisect_left(nums, x) returns the position where x can be inserted without breaking the order. If x is in the list, this is the index of its first occurrence:

import bisect

nums = [3, 8, 15, 21, 30, 42, 57]
i = bisect.bisect_left(nums, 42)
print(i, nums[i])  # 5 42
j = bisect.bisect_left(nums, 10)
print(j, j < len(nums) and nums[j] == 10)  # 2 False

For 10, the function returned 2, the place between 8 and 15, not a "not found" signal. So check the index:

1. The index is less than the list's length. For a target greater than every element, the function returns len(nums), and without this check nums[j] would raise an IndexError.
2. The element at that index equals the target.

Common mistake

Binary search is run on an unsorted list:

import bisect

nums = [7, 1, 5, 3]
i = bisect.bisect_left(nums, 1)
print(i, nums[i] == 1)  # 0 False

There is no error, but the answer is wrong: 1 is in the list, yet the check says it is not. The search relies on only smaller numbers standing left of each element, but here 7 comes before 1. Sort the list before searching—nums.sort() or sorted(nums).

Key points

• Linear search checks the elements in turn: up to a million comparisons for a million elements.
• Binary search compares the target with the middle element and drops half, so it needs about 20 comparisons.
• The bounds lo and hi close in; once lo is greater than hi, the target is not in the list.
• The search works only on a sorted list, and an index from bisect_left must be checked.