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 g <= m <= d : le nouvel intervalle, [m+1, d] ou [g, m-1], est de largeur au plus d - g - 1. Le cas de base g > d (intervalle vide) renvoie None.