Algorithmes de recherche dichotomique et de seuil en Python

Première générale Spé · Mathématiques Spé 1ère

À retenir

• **Principe** : on compare l'élément cherché à la valeur médiane milieu = (debut + fin) // 2. - Si égal : élément trouvé. - Si inférieur : on restreint la recherche à la moitié gauche (fin = milieu - 1). - Si supérieur : on restreint la recherche à la moitié droite (debut = milieu + 1). • **Condition impérative** : la liste doit être impérativement **triée**. • **Boucle de contrôle** : while debut <= fin: garantit l'exploration complète.

Le cours

1. Recherche dichotomique dans une liste triée Pour chercher une valeur dans une liste triée par ordre croissant, on compare la valeur cherchée à l'élément du milieu de la zone restante, puis on ne garde que la moitié où elle peut se trouver. On repère la zone par deux indices debut et fin, et le milieu par (debut + fin) // 2. Recherche de 23 dans [3, 8, 12, 17, 23, 31, 40] : 1. debut = 0, fin = 6, milieu 3 : 17 debut = 4. 2. Milieu (4 + 6) // 2 qui vaut 5 : 31 > 23, donc fin = 4. 3. Milieu 4 : L[4] vaut 23, trouvé en 3 comparaisons. 2. Efficacité Une recherche séquentielle peut demander n comparaisons pour n éléments. Par dichotomie, chaque tour sans succès garde au plus la moitié des éléments, donc le nombre maximal de tours est le plus petit entier k tel que 2^k > n : 3 tours pour 7 éléments, 10 pour 1\,000, 20 pour un million. 3. Algorithme de seuil Pour trouver le premier rang où une suite franchit un seuil, on calcule les termes un par un dans une boucle while dont la condition est le contraire de la condition d'arrêt. Exemple : premier n tel que u_n = 1\,000 0,5^n soit inférieur à 1. u = 1000 n = 0 while u >= 1: u = 0.5 * u n = n + 1 La boucle s'arrête avec n = 10 : u_9 1,95 1 et u_10 0,98 4. Attention Sur une liste non triée, la dichotomie peut répondre « absent » alors que la valeur est présente. Et la condition while debut <= fin (avec <=) est indispensable pour examiner une zone réduite à un seul élément.

Dans ce chapitre