Recherche linéaire et recherche dichotomique

La recherche dichotomique retrouve une valeur dans une liste triée en coupant la liste en deux à chaque étape. Pour un million de valeurs, elle demande au plus 20 comparaisons, contre un million pour la recherche linéaire.

Une université garde un fichier trié de 40 000 numéros de carte étudiante. Retrouver une carte à la main demande de la patience. Avec la bonne méthode, 16 cases suffisent.

La recherche linéaire commence à la première case et avance jusqu’à trouver la valeur. Elle marche sur toute liste, triée ou non.

Dans le pire des cas, la valeur est en dernière place ou absente : il faut regarder les n cases. Sa complexité est donc linéaire, O(n).

# Recherche linéaire dans la liste des numéros de carte.
cartes = [3, 9, 14, 21, 28, 37, 45, 52, 60, 71, 83]
cible = 21
pas = 0
trouve = -1
for i in range(len(cartes)):
    pas = pas + 1  # une comparaison
    if cartes[i] == cible:
        trouve = i
        break
print("indice :", trouve, "en", pas, "étapes")
# Cherchez 100, qui n’est pas dans la liste.

Dans une liste triée, on regarde la case du milieu. Si la valeur est plus grande que la cible, la cible ne peut pas être à droite : on écarte toute la moitié de droite.

Si elle est plus petite, on écarte la moitié de gauche. On recommence sur la moitié qui reste, jusqu’à trouver la cible ou n’avoir plus de case.

# Recherche dichotomique : la liste doit être triée.
cartes = [3, 9, 14, 21, 28, 37, 45, 52, 60, 71, 83]
cible = 21
debut = 0
fin = len(cartes) - 1
pas = 0
trouve = -1
while debut <= fin and trouve == -1:
    milieu = (debut + fin) // 2
    pas = pas + 1  # on regarde une seule case
    if cartes[milieu] == cible:
        trouve = milieu
    elif cartes[milieu] < cible:
        debut = milieu + 1
    else:
        fin = milieu - 1
print("indice :", trouve, "en", pas, "étapes")
# Cherchez 83, puis 50.

À chaque étape, la zone à explorer est divisée par deux. Une liste de 1 000 cases passe à 500, 250, 125, et ainsi de suite jusqu’à une seule case.

Le pire des cas vaut donc environ le nombre de fois qu’on peut diviser n par deux : c’est la complexité logarithmique, O(log n). Elle bat la recherche linéaire dès que la liste est un peu longue.

Trier une liste coûte plus cher qu’une seule recherche linéaire. Trier d’abord ne vaut donc pas la peine pour une seule recherche.

Il devient utile quand on cherche souvent dans la même liste : le tri se paie une fois, puis chaque recherche coûte peu. Un annuaire est trié pour cette raison.

seq 1 1000 | grep -n -x 700

python3 -c "print(1000 .bit_length())"

python3 -c "print((10 ** 6).bit_length())"

printf '5\n12\n7\n' | sort | xargs