Ordonner avant de parcourir : deux nombres de somme donnée

(* Renvoie Some (a, b) avec a + b = c, a et b à des indices distincts de t,
   ou None s'il n'en existe pas.
   Précondition : aucune. Le tableau n'est pas modifié (on travaille sur une copie).
   Complexité : Theta(n log n) pour le tri, puis Theta(n). *)
let paire t c =
  let u = Array.copy t in
  Array.sort compare u;
  let g = ref 0 and d = ref (Array.length u - 1) and rep = ref None in
  (* INVARIANT : si une paire de somme c existe dans u, alors il en existe une
     dont les deux indices sont dans [g, d]. *)
  while !rep = None && !g < !d do
    let s = u.(!g) + u.(!d) in
    if s = c then rep := Some (u.(!g), u.(!d))
    else if s < c then incr g          (* u.(g) est trop petit pour TOUT le monde *)
    else decr d                        (* u.(d) est trop grand pour TOUT le monde *)
  done;
  !rep

Terminaison. Variant : $d-g$. Chaque tour incrémente $g$ ou décrémente $d$, donc le variant décroît strictement d'au moins $1$ et reste minoré par $-1$. La boucle fait au plus $n-1$ tours.

Correction. L'invariant tient à l'initialisation : $[g,d]$ est tout le tableau. Il est préservé. Supposons $u_g+u_d<c$. Pour tout $j\le d$, on a $u_g+u_j\le u_g+u_d<c$ : aucune paire contenant $u_g$ à l'intérieur de $[g,d]$ n'atteint $c$. Écarter $g$ ne perd donc rien. Le cas $u_g+u_d>c$ est symétrique. À la sortie, ou bien on a trouvé, ou bien $g\ge d$ : l'intervalle ne contient plus de paire, donc il n'en existait aucune.

Le gain, mesuré sur t = [|31; 4; 17; 9; 25; 2; 48; 13; 36; 7|] :

Le point de méthode. Le tri coûte $\Theta (n\log n)$ une fois, et achète une monotonie : dans un tableau trié, savoir que $u_g+u_d<c$ élimine $d-g$ paires d'un coup. Sans le tri, une comparaison n'élimine qu'une paire. C'est le sens exact de la recommandation du programme — « ordonner les données avant de les parcourir ».