Recherche d'un élément dans un tableau

Pour déterminer si un élément est présent dans un tableau, on peut simplement parcourir les éléments du tableau un par un :

def recherche(element, tab):
    """
    tab - list, tableau d'éléments d'un type A
    element - de type A
    Sortie: bool - True si element est dans tab, False sinon.
    """
    for x in tab:
        if element == x:
            return True
    return False

En notant n la longueur du tableau tab passé en argument, la fonction recherche() effectuera de 1 à n comparaisons.

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

Exemple

La valeur 12 est-elle présent dans le tableau [1, 3, 4, 5, 7, 9, 11, 14, 15, 16, 17, 21] ?

1. En utilisant la fonction recherche(), il faut parcourir tous les éléments de ce tableau pour aboutir à la conclusion que 12 n'est pas un élément de celui-ci. Dans ce cas, 12 comparaisons ont été effectuées.

2. Avec un petit coup d'oeil, on peut voir que tous les éléments de ce tableau sont triés. Vous avez donc dû parcourir du regard les premiers éléments, jusqu'à lire les valeurs « 11 » puis « 14 » pour constater que 12 n'était pas un élément de ce tableau. Dans ce cas, 8 comparaisons ont été effectuées.

Problématique

Est-il possible d'être encore plus efficace ?