Structures de données et algorithmes · Recherche et tri

Recherche binaire

Diviser en deux, de façon répétée, une plage triée pour trouver une cible en temps logarithmique.

Commencer une leçon sur Recherche binaire

À apprendre d'abord

• Tableaux: Un bloc de mémoire contigu à disposition fixe, où n'importe quel index est atteint en temps constant.

Mène à

• Arbres binaires de recherche: Un arbre binaire maintenu ordonné pour que le sous-arbre gauche de chaque nœud soit plus petit et le droit plus grand.

Notions liées

• Deux pointeurs: Faire avancer deux indices à travers une séquence en même temps pour éviter une boucle imbriquée.
• Diviser pour régner: Découper un problème en copies indépendantes plus petites de lui-même, résoudre chacune, puis combiner.