Numérique et sciences informatiques (spécialité) · Première · Algorithmique

Recherche dichotomique

• La recherche dichotomique trouve la position d'une valeur dans un tableau trié en comparant la valeur cherchée à l'élément du milieu, puis en gardant une seule moitié.
• À chaque tour de boucle, la zone de recherche est divisée par 2 : on dit qu'on procède par dichotomie.
• Le nombre de comparaisons est logarithmique en la taille du tableau, alors que la recherche séquentielle est linéaire.
• La boucle while n'est pas bornée à l'avance : on prouve qu'elle s'arrête avec un variant et qu'elle est correcte avec un invariant.