Leçon 8 : recherche binaire

Jouons à un jeu de devinette : j'ai pensé à un nombre entre 1 et 100, et à chaque essai je dis « trop haut » ou « trop bas ». La méthode intelligente : deviner le milieu à chaque fois et éliminer la moitié des possibilités. C'est exactement la « recherche binaire » — un algorithme qui trouve une val

La recherche binaire, c'est comme chercher un mot dans un épais dictionnaire : tu ne lis pas page par page depuis le début. Tu ouvres au milieu, et si ton mot vient plus tard dans l'alphabet — tu jettes toute la première moitié d'un coup. Chaque coup d'œil coupe en deux ce qu'il reste à chercher.

recherche binaire: Un algorithme de recherche sur un tableau trié qui, à chaque étape, vérifie le milieu et élimine la moitié qui ne peut pas contenir la cible — O(log n).
temps logarithmique: O(log n) : le nombre d'étapes grandit très lentement — chaque doublement de n n'ajoute qu'une seule étape, car l'espace de recherche est coupé en deux à chaque fois.
espace de recherche: La plage d'index [low, high] qui peut encore contenir la cible ; la recherche binaire la réduit de moitié à chaque itération.