Recherche binaire : réduire la recherche de moitié — 7–10
Quand une liste est déjà rangée, tu n’as pas besoin de vérifier chaque élément un par un. La recherche binaire regarde le milieu, choisit la moitié où la réponse peut se trouver et recommence jusqu’à la trouver ou l’écarter.
Couper les possibilités en deux
Imagine qu’un nombre secret se trouve dans une rangée ordonnée. Au lieu de commencer par le premier, demande le nombre du milieu. Si la cible est plus grande, écarte la moitié basse ; si elle est plus petite, écarte la moitié haute. Chaque réponse enlève environ la moitié des choix, donc la recherche rétrécit vite.
Pourquoi ne pas vérifier chaque élément ?
Commencer au début convient à une petite liste, mais devient lent avec des milliers ou des millions d’éléments ordonnés. La recherche binaire utilise l’ordre comme indice au lieu de le gaspiller. Elle vient d’une question simple : comment éliminer le plus de mauvaises places possible avec une seule vérification ?
Trouver 73 dans une liste
La liste ordonnée est 12, 25, 31, 44, 58, 73, 81, 90. D’abord, vérifie le milieu : 44. Comme 73 est plus grand, garde 58, 73, 81, 90. Vérifie le milieu de ce groupe : 73. La cible est trouvée en deux vérifications, au lieu de parcourir les huit nombres.
L’ordre est indispensable
Il semble raisonnable de regarder le milieu de n’importe quelle liste, car le milieu paraît être un bon raccourci. Mais dans 12, 90, 25, 73, 44, 81, 31, 58, voir 44 ne dit pas dans quelle moitié se trouve 73. La recherche binaire fonctionne seulement si la liste est ordonnée selon ce que tu compares.
Trouver rapidement
Un dictionnaire suit l’ordre alphabétique : tu peux l’ouvrir vers le milieu et réduire la recherche d’un mot. Les programmes utilisent la même stratégie avec des noms, des nombres et des fiches ordonnés. C’est utile pour une grande liste déjà rangée ; la ranger d’abord demande parfois un travail supplémentaire.
Continue d'explorer
Autres langues
Chargement de MyLeoNes™…