Adloun

Point d'insertion

Exercice · OCaml (option informatique), chapitre 10 — Recherche et dichotomie

Énoncé

É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).

Corrigé

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 &lt; x et les &gt;= 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.)

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.