La recherche binaire trouve une valeur dans une collection triée en comparant la valeur cherchée à l'élément du milieu, puis en éliminant la moitié des candidats à chaque étape. Sa complexité est en O(log n). Elle ne fonctionne que si les données sont triées et accessibles par indice.
Exemple
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)