Introduction

La recherche par dichotomie est un des algorithmes qui nécessite comme condition d'avoir une liste triée. Cet algorithme a pour but de trouver rapidement une valeur dans une liste triée.

Problème

Entrée :

• Liste triée d'éléments
• Valeur à rechercher

Sortie :

• Booléen indiquant la présence ou l'absence de la valeur indiquée dans la liste.

Un premier algorithme pour résoudre ce problème est l'algorithme de parcours séquentiel d'une liste. Cet algorithme consiste à parcourir un à un tous les éléments de la liste, jusqu'à trouver la valeur recherchée, ou atteindre la fin de la liste. Il s'agit d'un algorithme ayant une complexité linéaire \(\mathcal{O}(n)\) avec \(n\) étant le nombre d'éléments dans la liste.

L'algorithme de recherche par dichotomie (du grec ancien dikhotomia signifiant division en deux parties) consiste à chercher la valeur en vérifiant au centre de la liste. Si la valeur recherchée est plus petite que l'élément présent au centre de la liste, on recommence avec la sous-liste des éléments avant cet élément. Et à l'inverse, si la valeur recherchée est plus grande que l'élément au centre de la liste, on recommence avec la sous-liste des éléments après cet élément.

On applique déjà cet algorithme quand on doit deviner une valeur entre deux bornes, par exemple dans Le Juste Prix où le joueur doit trouver un nombre avec l'aide du présentateur qui répond plus petit ou plus grand.