Recherche dichotomique

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.