Binary Search in Python

A binary search in Python keeps track of the remaining range of the list using three variables: first, last and middle. first holds the position of the first item in the current range and last holds the position of the last item. middle is the position halfway through that range, calculated from the two bounds:

middle = (first + last) // 2

The // operator is integer division, so the result is rounded down. When the range has an even number of items there are two middle items, and rounding down selects the left-hand one. For example, with first at 0 and last at 7, the calculation gives 3, the left item of the pair at positions 3 and 4.

The loop and its comparisons

The search runs in a loop that continues while the current range still contains items, written in Python as while first <= last. Inside the loop the item at middle is compared with the target:

• If they are equal, the item has been found and middle is reported as its position.
• If the target is smaller, last becomes middle - 1, discarding the middle item and everything above it.
• If the target is larger, first becomes middle + 1, discarding the middle item and everything below it.

Setting a bound to just beyond middle removes the middle item as well as one whole half of the list, so each comparison roughly halves the items left to check.

When first becomes greater than last, the range is empty and the loop finishes, so the search reports that the target is not in the list. The program returns -1 rather than a position, because -1 can never be a real index.

distances = [4, 9, 13, 18, 22, 27, 31, 36, 40]
wanted = 27

def find_position(values, goal):
    first = 0
    last = len(values) - 1
    while first <= last:
        middle = (first + last) // 2
        if values[middle] == goal:
            return middle
        elif values[middle] < goal:
            first = middle + 1
        else:
            last = middle - 1
    return -1

print(find_position(distances, wanted))

Output:

5