Binary search

Binary search finds a value in a sorted collection by comparing the target to the middle element, then eliminating half of the candidates at each step. Its complexity is O(log n). It only works if the data is sorted and accessible by index.

def cherche(t, x):
    g, d = 0, len(t) - 1
    while g <= d:
        m = (g + d) // 2
        if t[m] == x: return m
        g, d = (m + 1, d) if t[m] < x else (g, m - 1)

The whole glossary