Dichotomiser sur les valeurs candidates, et non sur les réels

L'observation. Dans une couverture optimale, un segment commence sur un point (sinon on le décale vers la droite) et son extrémité droite touche un point (sinon on le raccourcit, ainsi que tous les autres). La longueur optimale est donc de la forme $x_j-x_i$. Il y a au plus $\left(\genfrac{}{}{0ex}{}{n}{2}\right)+1$ telles valeurs.

La version exacte. On dichotomise sur le rang dans le tableau trié des écarts, et non sur un intervalle de réels.

(* Plus petite longueur permettant de couvrir x par k segments égaux.
   Précondition : x trié, non vide, k >= 1. Résultat EXACT, aucun epsilon.
   Complexité : Theta(n^2 log n) pour trier les écarts, puis Theta(n log n)
   pour la dichotomie ; on peut descendre à Theta(n log n) au total en
   dichotomisant sur la valeur entière quand les points sont entiers. *)
let longueur_exacte x k =
  let n = Array.length x in
  let cand = ref [] in
  for i = 0 to n - 1 do for j = i to n - 1 do
    cand := (x.(j) -. x.(i)) :: !cand done done;
  let c = Array.of_list !cand in
  Array.sort compare c;
  let g = ref 0 and d = ref (Array.length c - 1) in
  (* INVARIANT : la réponse est c.(r) pour un r dans [g, d]. *)
  while !g < !d do
    let m = !g + (!d - !g) / 2 in
    if segments_necessaires x c.(m) <= k then d := m else g := m + 1
  done;
  c.(!g)

Noter l'affectation g := m + 1 et non g := m : voir l'exercice 15.10, où l'oubli de ce $+1$ fait boucler.

La mesure, sur les points $1,2,5,9,10,14,20,21$ :

La dichotomie flottante a fait $35$ tours à chaque fois ; l'exacte en fait $\lceil {\log }_{2}36\rceil =6$, sur les $36$ écarts distincts.

Les deux gains, et le second est le vrai. Le premier est le nombre de tours. Le second est la disparition de $\epsilon$ : à $k=8$ la réponse est $0$, et la version flottante rend $10^{-9}$. Cette valeur n'est pas la réponse, c'est la précision du calcul — et elle se propagera dans tout ce qui l'utilise. Un algorithme qui rend un $\epsilon$ ne résout pas le problème posé ; il résout un problème voisin.

Quand garder la version flottante. Quand les candidats sont trop nombreux pour être énumérés — ici $\Theta (n^2)$ —, ou quand la réponse n'est pas de forme connue. La dichotomie réelle reste alors la bonne méthode, avec son $\epsilon$ assumé et documenté.