Algorithmes de recherche

La « recherche » recouvre plusieurs problèmes : localiser une valeur dans une séquence, interroger un ensemble ordonné, retrouver une clé ou découvrir les sommets accessibles d’un graphe. Choisissez la représentation avant l’algorithme.

Carte de décision

Situation	Méthode	Coût typique	Exigence principale
Un parcours de données non triées	recherche linéaire	$O(n)$	test d’égalité
Séquence triée à accès aléatoire	recherche binaire	$O(\log n)$	ordre maintenu
Recherches répétées par clé exacte	table de hachage	$O(1)$ espéré	hachage et espace supplémentaire
Ensemble dynamique ordonné / intervalles	arbre équilibré	$O(\log n)$	maintenance de l’arbre
Exploration profonde / dépendances	DFS	$O(V+E)$	état de visite
Chemins au nombre minimal d’arêtes dans un graphe non pondéré	BFS	$O(V+E)$	file et état de visite

Ces coûts supposent des implémentations classiques. Le pire cas d’une table de hachage n’est pas constant, et un arbre déséquilibré peut atteindre une hauteur linéaire.

Amortir le prétraitement

Trier pour permettre la recherche binaire coûte $O(n\log n)$. Cet investissement est utile pour de nombreuses requêtes ou si les opérations ordonnées sont aussi nécessaires ; il est souvent inutile pour une seule recherche. Une table de hachage échange de même construction et mémoire contre des recherches exactes répétées.

La recherche est souvent un problème de frontière

La recherche binaire se généralise de « trouver cette valeur » à « trouver la première position où un prédicat monotone devient vrai ». DFS et BFS deviennent eux aussi utiles lorsque le contrat de sortie est précisé : existence, ordre de parcours, parents, distances, composantes ou chemin témoin.

Compter toute la charge de travail

Pour un tableau statique et $q$ requêtes, les parcours linéaires répétés coûtent $O(qn)$. Trier une fois puis chercher par dichotomie coûte $O(n\log n+q\log n)$, plus les copies ou la conservation des indices initiaux. Le modèle à coût unitaire suggère un croisement vers un nombre logarithmique de requêtes nécessitant un parcours complet, pas un seuil mesuré universel. Des mises à jour fréquentes changent le calcul : insérer dans un tableau trié déplace encore $O(n)$ éléments, même si bisect trouve la position en temps logarithmique.

Les recherches séquentielles renvoient des positions ou frontières d’insertion ; les parcours de graphes renvoient des sommets accessibles et des informations de chemin. Avec des listes d’adjacence, $V$ et $E$ comptent les sommets et arêtes de la partie parcourue, pas la longueur d’une séquence. Une source unique ne couvre pas les composantes déconnectées. Un simple test d’existence peut s’arrêter tôt ; obtenir tous les sommets accessibles ou toutes les distances exige de terminer le parcours.

Sources

• Open Data Structures
• Python bisect

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.