La recherche dichotomique est un algorithme de recherche pour trouver la position d’un élément dans un tableau trié. Le principe est le suivant : comparer l’élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente.
Le nombre de comparaisons, est logarithmique en la taille du tableau. Il y a de nombreuses structures spécialisées (comme les tables de hachage) qui peuvent être recherchées plus rapidement, mais la recherche dichotomique s’applique à plus de problèmes.
La dichotomie possède une complexité algorithmique logarithmique en le nombre d’éléments composant le tableau dans lequel s’effectue la recherche.
On considère dans un premier temps le nombre de comparaisons comme étant la mesure de complexité. On appelle T(n) le nombre de comparaisons effectuées pour une instance de taille n. Alors le nombre de comparaisons T satisfait la récurrence suivante : T(n)=1+T(n/2). D’après le « master theorem », cette récurrence a une solution de la forme T(n)=O(log(n)), avec la notation de Landau. Enfin le nombre de comparaisons est linéaire en le nombre d’opérations effectuées; l’algorithme a donc une complexité logarithmique.
Aucune réponse