(* Déterminer si une valeur v apparaît dans un tableau d'entiers a,
   en supposant le tableau trié par ordre croissant.
   On peut donc effectuer une recherche dichotomique (binary search)
   et la complexité est logarithmique en la taille du tableau. *)

(* On généralise en une fonction qui cherche dans a[lo..hi[
   c'est-à-dire seulement entre les indices lo inclus et hi exclus. *)

let rec binary_search a v lo hi =
  lo < hi &&
  let mid = lo + (hi - lo) / 2 in
  a.(mid) = v ||
  if v < a.(mid) then binary_search a v lo mid else binary_search a v (mid+1) hi

(* note : on évite de calculer la moyenne de lo et hi avec (lo+hi)/2
   car cela peut provoquer un débordement de capacité avec des entiers
   32 bits et un tableau très grand. *)

(* on en déduit la fonction qui cherche dans l'intégralité du tableau *)

let binary_search a v =
  binary_search a v 0 (Array.length a)

(* quelques tests *)

let () =
  let test a v b = assert (binary_search a v = b) in
  test [||] 1 false;
  test [|42|] 42 true;
  test [|-1;1|] 0 false;
  let a = Array.init 10 (fun i -> i) in
  for i = 0 to 9 do test a i true done;
  test a 10 false

This document was generated using caml2html