Dichotomie récursive

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.