Algorithmes : la recherche dichotomique (diviser pour trouver vite)

Algorithme

def chercher(t, x):
    debut, fin = 0, len(t) - 1
    while debut <= fin:
        milieu = (debut + fin) // 2
        if t[milieu] == x: return milieu
        if t[milieu] < x: debut = milieu + 1
        else: fin = milieu - 1
    return -1

Efficacité

Recherche linéaire : jusqu'à n comparaisons. Dichotomique : environ log₂(n) — 20 pour un million, 30 pour un milliard. Condition : données triées.

En pratique

import bisect
i = bisect.bisect_left(nombres, 1_234_568)

Même principe : git bisect pour trouver le commit qui a introduit un bug, le jeu du « plus grand / plus petit » (boucles). Voir les tris.