Binary Search

Understand the idea

This version uses an inclusive left and right interval and returns an index or None. Every comparison removes the examined midpoint and the half that cannot contain the target. Time grows logarithmically on indexed sequences, while sorting the input first has its own cost. Python's bisect module supplies useful insertion-point operations.

Where to try it

Open this example with Try in playground. The code loads as editable text and does not run until you select Run. The first run downloads Python. Each run starts fresh; temporary files created by a script are not files on your PC.

A worked example

def binary_search(values, wanted):
    left, right = 0, len(values) - 1
    while left <= right:
        middle = (left + right) // 2
        if values[middle] == wanted:
            return middle
        if values[middle] < wanted:
            left = middle + 1
        else:
            right = middle - 1
    return None

print(binary_search([2, 4, 7, 9], 7))

Read the result

The result is index 2.

Try one change

Test empty input, both endpoints, and a value between two existing items.