Recherche par dichotomie

Pour chercher un élément dans une liste, on peut simplement parcourir les éléments de la liste un par un:

def recherche(element, tab):
    """
    tab -- liste d'éléments d'un type A
    element -- de type A

    renvoie True si element est dans tab, False sinon.
    """
    for x in tab:
        if element == x: return True
    return False

Si l'on note n la longueur de la liste tab passée en argument, on effectuera de 1 à n comparaisons.

Pour une liste quelconque, on ne peut pas améliorer ce nombre de comparaisons.
Mais lorsque la liste satisfait certaines préconditions, la recherche peut être plus efficace.