Terminale · Numérique et sciences informatiques

Utiliser la recherche dichotomique et les idées de fusion : diviser pour régner sur une liste triée

Mettre en œuvre une recherche dichotomique sur un tableau trié, justifier sa terminaison et sa correction par un variant et un invariant, et exploiter la fusion de deux listes triées pour rechercher ou combiner des données.

Aperçu gratuit
Illustration de la fiche « Utiliser la recherche dichotomique et les idées de fusion : diviser pour régner sur une liste triée »

Les points essentiels

  • La recherche dichotomique ne s'applique qu'à un tableau trié : à chaque étape, on compare la valeur cherchée à l'élément du milieu et on élimine la moitié de la zone de recherche qui ne peut pas contenir la valeur.
  • Le coût est logarithmique : pour un tableau de n éléments, il faut au plus environ log2(n) comparaisons, contre n pour une recherche séquentielle dans le pire cas. Pour 1 000 000 d'éléments, environ 20 comparaisons suffisent.

Les mots à connaître

Recherche dichotomique
Algorithme de recherche dans un tableau trié qui, à chaque étape, compare la valeur cherchée à l'élément central et ne conserve que la moitié du tableau où elle peut se trouver, jusqu'à la trouver ou jusqu'à ce que la zone soit vide.
Variant de boucle
Quantité entière positive ou nulle qui décroît strictement à chaque itération ; son existence prouve que la boucle se termine. Ici : la taille de la zone de recherche.

Un exemple pour comprendre

Soit le tableau trié t = [2, 5, 8, 12, 16, 23, 38, 56]. Déroule la recherche dichotomique de la valeur 23 en indiquant debut, fin et milieu à chaque tour.

Au départ debut = 0, fin = 7. Tour 1 : milieu = (0+7)//2 = 3, t[3] = 12. Comme 23 > 12, on pose debut = 4. Tour 2 : debut = 4, fin = 7, milieu = (4+7)//2 = 5, t[5] = 23. C'est égal à la valeur cherchée : on retourne l'indice 5. Il a suffi de 2 comparaisons au lieu de 6 pour une recherche séquentielle.

Première page de l’Essentiel : Utiliser la recherche dichotomique et les idées de fusion : diviser pour régner sur une liste triée
Ketty