Recherche et dichotomie

10.1 Introduction et motivation

Chercher un élément dans une collection est l'opération la plus courante de toute l'informatique. Si la collection est quelconque, on n'a d'autre choix que de la parcourir : c'est la recherche séquentielle, en $\Theta (n)$. Mais si elle est triée, on peut faire infiniment mieux : à chaque comparaison, on élimine la moitié des candidats. C'est la dichotomie, en $\Theta (\log n)$ — un gain spectaculaire (chercher dans un million d'éléments triés ne demande qu'une vingtaine de comparaisons).

Ce chapitre prolonge la partie algorithmique. On y étudie la recherche dichotomique et sa preuve (invariant, variant), puis la même idée du « diviser par deux » appliquée au calcul de puissances (exponentiation rapide) et à la recherche d'un seuil sur un intervalle. Le fil rouge : réduire de moitié à chaque étape mène au logarithme.

10.2 La recherche séquentielle

Sans hypothèse sur les données, on parcourt jusqu'à trouver (rappel du chapitre 5) :

let recherche x t =
  let n = Array.length t in
  let i = ref 0 and trouve = ref None in
  while !i < n && !trouve = None do
    if t.(!i) = x then trouve := Some !i;
    i := !i + 1
  done;
  !trouve

Coût $\Theta (n)$ dans le pire cas (élément absent ou en fin). Sur une liste, on ferait de même par récursion. C'est inévitable tant qu'on ignore tout de l'ordre des éléments.

10.3 La recherche dichotomique

Si le tableau est trié, on compare l'élément cherché à celui du milieu : selon le résultat, on poursuit dans la moitié gauche ou droite, jamais les deux.