Recherche et dichotomie

Cours complet · OCaml (option informatique), chapitre 10 · prépas MPSI et MP, option informatique

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>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 $Θ (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 $Θ (lo g 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 $Θ (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.


let dichotomie x t =
  let g = ref 0 and d = ref (Array.length t - 1) and trouve = ref None in
  while !g <= !d && !trouve = None do
    let m = (!g + !d) / 2 in
    if t.(m) = x then trouve := Some m
    else if t.(m) < x then g := m + 1
    else d := m - 1
  done;
  !trouve

Méthode : Invariant et variant de la dichotomie

Invariant : si x figure dans le tableau, alors son indice est dans l'intervalle [g, d]. Au départ [0, n-1] (tout le tableau) ; à chaque tour, on élimine la moitié qui ne peut contenir x (le tableau étant trié). Variant : la largeur d - g + 1 de l'intervalle de recherche, qui décroît strictement (au moins de moitié) à chaque tour — d'où la terminaison et le coût $Θ (lo g n)$ .

ImportantLa dichotomie exige un accès direct

Diviser par deux suppose d'atteindre la case du milieu en temps constant : c'est le propre du tableau. Sur une liste, accéder au milieu coûte déjà $Θ (n)$ , ce qui ruine l'intérêt de la dichotomie. Tableau trié et dichotomie vont de pair.

La version récursive dit la même chose, en passant les bornes en arguments :


let rec dicho_rec x t g d =
  if g > d then None
  else
    let m = (g + d) / 2 in
    if t.(m) = x then Some m
    else if t.(m) < x then dicho_rec x t (m + 1) d
    else dicho_rec x t g (m - 1)

10.4 L'exponentiation rapide

Le calcul de $x^{n}$ par $n$ multiplications (chapitre 4) coûte $Θ (n)$ . On fait bien mieux en remarquant que $x^{n} = (x^{n /2})^{2}$ (au facteur $x$ près si $n$ est impair) : on divise l'exposant par deux à chaque étape.


let rec puissance_rapide x n =
  if n = 0 then 1
  else
    let p = puissance_rapide x (n / 2) in
    if n mod 2 = 0 then p * p
    else p * p * x

Complexité : Exponentiation rapide

On nomme p = $x^{n /2}$ pour ne le calculer qu'une fois (l'écrire deux fois doublerait le travail à chaque étage et ruinerait le gain !). L'exposant est divisé par deux à chaque appel : il y a $Θ (lo g n)$ appels, donc $Θ (lo g n)$ multiplications, contre $Θ (n)$ pour la version naïve. Pour $n = 1000$ , dix multiplications environ au lieu de mille.

10.5 Dichotomie sur un intervalle

La dichotomie ne sert pas qu'à chercher dans un tableau : elle s'applique à toute recherche d'un seuil sur une quantité monotone. On cherche, dans un intervalle d'entiers, la frontière entre « ça ne convient pas » et « ça convient ».

Exemple 10.1Plus petit indice satisfaisant un prédicat

Soit p : int -> bool croissant (faux, puis vrai à partir d'un certain point). On trouve le plus petit x de [a, b] tel que p x, en supposant p b = true :


let premier_vrai p a b =
  let g = ref a and d = ref b in
  while !g < !d do
    let m = (!g + !d) / 2 in
    if p m then d := m else g := m + 1
  done;
  !g

Invariant : p !d est vrai (d convient toujours) et p (!g - 1) est faux. Quand g = d, c'est la frontière cherchée. Variant : d - g.

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>10.6 Exercices résolus

Niveau $⋆$ (application directe du cours)

Exercice 1 : Recherche séquentielle

Écrire recherche x t renvoyant Some i (première position) ou None. Quel est son coût ?

Démonstration


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 $Θ (n)$ au pire (parcours complet). On s'arrête dès qu'on a trouvé grâce à la condition !trouve = None.

Exercice 2 : Recherche dichotomique

Écrire dichotomie x t sur un tableau trié, et l'illustrer sur [|2; 5; 8; 12; 16|] avec x = 12.

Démonstration


let dichotomie x t =
  let g = ref 0 and d = ref (Array.length t - 1) and trouve = ref None in
  while !g <= !d && !trouve = None do
    let m = (!g + !d) / 2 in
    if t.(m) = x then trouve := Some m
    else if t.(m) < x then g := m + 1
    else d := m - 1
  done;
  !trouve

Sur [|2;5;8;12;16|], x=12 : m=2, t.(2)=8 < 12 → g=3 ; m=3, t.(3)=12 → Some 3. Deux comparaisons au lieu de quatre.

Exercice 3 : Exponentiation rapide

Écrire puissance_rapide x n et compter le nombre de multiplications pour n = 8.

Démonstration


let rec puissance_rapide x n =
  if n = 0 then 1
  else
    let p = puissance_rapide x (n / 2) in
    if n mod 2 = 0 then p * p
    else p * p * x

Pour n=8 : appels sur $8, 4, 2, 1, 0$ . À chaque retour (sauf le cas $0$ ), un ou deux produits : $x^{8} = (x^{4})^{2}$ , etc. — de l'ordre de $lo g_{2} 8 = 3$ élévations au carré, contre $8$ multiplications pour la version naïve.

Niveau $⋆ ⋆$ (raisonnement intermédiaire)

Exercice 4 : Dichotomie récursive

Écrire dicho_rec x t g d (version récursive) et donner son variant.

Démonstration


let rec dicho_rec x t g d =
  if g > d then None
  else
    let m = (g + d) / 2 in
    if t.(m) = x then Some m
    else if t.(m) < x then dicho_rec x t (m + 1) d
    else dicho_rec x t g (m - 1)

Variant : d - g (la largeur de l'intervalle), qui décroît strictement à chaque appel car m est strictement entre g et d (sauf intervalle minuscule, où l'on tranche). Le cas de base g > d (intervalle vide) renvoie None.

Exercice 5 : Logarithme contre linéaire

Sur un tableau trié de $n = 1000$ éléments, combien de comparaisons au pire pour la recherche séquentielle ? pour la dichotomie ? Commenter.

Démonstration

Séquentielle : jusqu'à $1000$ comparaisons. Dichotomie : à chaque étape la largeur est divisée par deux, donc au plus $⌈ lo g_{2} 1000 ⌉ = 10$ comparaisons. Le rapport est de $100$ : c'est tout l'intérêt de trier une fois pour chercher souvent (le coût du tri, $Θ (n lo g n)$ , s'amortit sur de nombreuses recherches).

Exercice 6 : Première occurrence

Sur un tableau trié avec doublons, écrire premiere_occ x t : l'indice de la première occurrence de x, ou None.

Démonstration


let premiere_occ x t =
  let g = ref 0 and d = ref (Array.length t - 1) and res = ref None in
  while !g <= !d do
    let m = (!g + !d) / 2 in
    if t.(m) = x then begin res := Some m; d := m - 1 end  (* continuer à gauche *)
    else if t.(m) < x then g := m + 1
    else d := m - 1
  done;
  !res

Quand on trouve x, on le note mais on continue à chercher plus à gauche (d := m - 1) : la dernière trouvaille avant épuisement est la plus à gauche. C'est une dichotomie qui ne s'arrête pas à la première égalité.

Exercice 7 : Point d'insertion

Écrire insertion x t : l'indice où insérer x dans le tableau trié t pour le garder trié (le nombre d'éléments < x).

Démonstration


let insertion x t =
  let g = ref 0 and d = ref (Array.length t) in   (* d exclusif *)
  while !g < !d do
    let m = (!g + !d) / 2 in
    if t.(m) < x then g := m + 1 else d := m
  done;
  !g

On cherche par dichotomie la frontière entre les < x et les >= x. g converge vers le nombre d'éléments strictement inférieurs à x : c'est exactement la position d'insertion. (Borne d prise exclusive ici, d'où Array.length t.)

Niveau $⋆ ⋆ ⋆$ (approfondissement)

Exercice 8 : Racine carrée entière par dichotomie

Écrire racine n ( $n \geq 0$ ), le plus grand $r$ tel que $r^{2} \leq n$ , en $Θ (lo g n)$ par dichotomie (à comparer au $Θ (n)$ du chapitre 4).

Démonstration


let racine n =
  let g = ref 0 and d = ref n in
  while !g < !d do
    let m = (!g + !d + 1) / 2 in   (* milieu « par excès » *)
    if m * m <= n then g := m
    else d := m - 1
  done;
  !g

On cherche le plus grand m avec mm <= n. Invariant : !g !g <= n (g est réalisable) et la réponse est dans [g, d]. Le milieu par excès (+1) est nécessaire : avec g := m et un milieu par défaut, on bouclerait sans fin quand d = g + 1. Variant : d - g. Coût $Θ (lo g n)$ . racine 10 $= 3$ .

Exercice 9 : Recherche d'un seuil monotone

Écrire premier_vrai p a b (plus petit x de [a, b] tel que p x, avec p croissant et p b vrai), puis l'utiliser pour retrouver racine.

Démonstration


let premier_vrai p a b =
  let g = ref a and d = ref b in
  while !g < !d do
    let m = (!g + !d) / 2 in
    if p m then d := m else g := m + 1
  done;
  !g

(* Plus grand r tel que r*r <= n : le seuil où (m+1)^2 > n commence. *)
let racine n =
  if n = 0 then 0
  else premier_vrai (fun m -> (m + 1) * (m + 1) > n) 0 n

premier_vrai encapsule une fois pour toutes le schéma de dichotomie sur un prédicat monotone. On l'instancie avec le prédicat « $(m + 1)^{2} > n$ » (croissant) : son plus petit point vrai est précisément $⌊ n ⌋$ . C'est la puissance des fonctions d'ordre supérieur : un algorithme, mille usages.

Exercice 10 : Exponentiation modulaire rapide

Écrire puissance_mod x n m calculant $x^{n} mod m$ en $Θ (lo g n)$ , sans jamais manipuler de très grands nombres.

Démonstration


let rec puissance_mod x n m =
  if n = 0 then 1 mod m
  else
    let p = puissance_mod x (n / 2) m in
    let p2 = (p * p) mod m in
    if n mod 2 = 0 then p2
    else (p2 * x) mod m

Même schéma que l'exponentiation rapide, mais on réduit modulo m après chaque produit : les valeurs restent bornées par m, ce qui évite les dépassements de capacité même pour de très grands exposants. C'est le cœur des calculs en arithmétique modulaire (cryptographie). $Θ (lo g n)$ multiplications.

Synthèse du chapitre (à retenir)

Recherche séquentielle : $Θ (n)$ , sans hypothèse sur les données.
Dichotomie (tableau trié) : comparer au milieu, éliminer une moitié ; $Θ (lo g n)$ . Invariant : la cible, si présente, est dans [g, d] ; variant : la largeur d - g + 1. Exige un accès direct (tableau, pas liste).
Exponentiation rapide : $x^{n} = (x^{n /2})^{2}$ (au facteur x près si impair) ; $Θ (lo g n)$ — nommer $x^{n /2}$ pour ne le calculer qu'une fois.
Dichotomie sur un prédicat monotone : trouver le seuil faux/vrai en $Θ (lo g)$ ; schéma générique (premier_vrai) réutilisable (racine entière, seuils…).
Le réflexe « diviser par deux à chaque étape » mène au coût logarithmique : recherche, puissance, seuil.

10.7 Exercices d'entraînement

Légende : $⋆$ application directe, $⋆ ⋆$ raisonnement intermédiaire, $⋆ ⋆ ⋆$ approfondissement ; $⧫$ signale un classique incontournable. La numérotation prolonge celle des dix exercices résolus.

Thème A — Recherches simples.

[11.] $⋆$ Écrire contient x t : bool par dichotomie (réutiliser dichotomie).
[12.] $⋆ ⋆$ Écrire compte_occ x t (nombre d'occurrences de x dans un tableau trié) en $Θ (lo g n)$ (deux dichotomies : première et dernière occurrence).
[13.] $⋆ ⋆$ $⧫$ Écrire derniere_occ x t (symétrique de premiere_occ).

Thème B — Exponentiation.

[14.] $⋆ ⋆$ Écrire puissance_rapide en version itérative (boucle while, en parcourant les bits de l'exposant).
[15.] $⋆ ⋆ ⋆$ Écrire fibo_rapide n en $Θ (lo g n)$ par exponentiation de la matrice $2 \times 2$ de Fibonacci.

Thème C — Dichotomie sur un prédicat.

[16.] $⋆ ⋆$ À l'aide de premier_vrai, écrire racine_cubique n (plus grand $r$ tel que $r^{3} \leq n$ ).
[17.] $⋆ ⋆ ⋆$ $⧫$ Recherche d'un zéro par dichotomie d'une fonction f : int -> int croissante (plus petit $x$ avec f x >= 0).
[18.] $⋆ ⋆ ⋆$ Étant donné premier_vrai, écrire dernier_vrai (plus grand point vrai d'un prédicat décroissant).

Thème D — Variantes et pièges.

[19.] $⋆ ⋆$ Pourquoi (g + d) / 2 et (g + d + 1) / 2 ne sont-ils pas interchangeables selon qu'on fait g := m ou d := m ? Donner un cas de boucle infinie.
[20.] $⋆ ⋆ ⋆$ Rechercher dans un tableau trié puis décalé circulairement (ex. [|4;5;6;1;2;3|]) : adapter la dichotomie.
[21.] $⋆ ⋆$ Écrire plus_proche x t : l'élément du tableau trié le plus proche de x (en valeur), en $Θ (lo g n)$ .
[22.] $⋆ ⋆ ⋆$ $⧫$ Discuter : pourquoi la dichotomie est-elle inadaptée à une liste chaînée, et que faudrait-il pour la rendre efficace ?

Continuer sur Adloun : animation, QCM, fiches, exercices

Recherche et dichotomie

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>10.1 Introduction et motivation

10.2 La recherche séquentielle

10.3 La recherche dichotomique

Méthode : Invariant et variant de la dichotomie

10.4 L'exponentiation rapide

Complexité : Exponentiation rapide

10.5 Dichotomie sur un intervalle

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>10.6 Exercices résolus

Niveau ⋆ (application directe du cours)

Niveau ⋆⋆ (raisonnement intermédiaire)

Niveau ⋆⋆⋆ (approfondissement)

10.7 Exercices d'entraînement

Thème A — Recherches simples.

Thème B — Exponentiation.

Thème C — Dichotomie sur un prédicat.

Thème D — Variantes et pièges.

Niveau $⋆$ (application directe du cours)

Niveau $⋆ ⋆$ (raisonnement intermédiaire)

Niveau $⋆ ⋆ ⋆$ (approfondissement)