(* Recherche dichotomique dans un tableau trié *)
(* Attention au travail papier pour voir les conséquences sur le choix de l'indice du milieu à n / 2 (division entière), en particuliers pour l'extraction des sous-tableaux ou les calculs des indices correspondants :
si n est impaire n = 2p + 1, m = p, il y a alors p indices inférieurs à m = p (de 0 à p - 1), et p indices supérieurs à m (de p + 1 à n - 1 = 2p)
si n est pair n = 2p, m = p, il y a encore p indices inférieurs à m = p (de 0 à p - 1) mais seulement p - 1 indices supérieurs à m (de p + 1 à n - 1 = 2p - 1 *)
(* Version avec extraction des sous-tableaux *)
let rec dicho (e : 'a) (t : 'a array) : bool =
  let n = Array.length t in
  if n = 0 then false
  else if n = 1 then t.(0) = e else
    let m = n / 2 in
    if t.(m) = e then true
    else if t.(m) > e then 
      dicho e (Array.sub t 0 m)
            else dicho e (Array.sub t (m + 1) (n - m - 1)) ;;

dicho 0 [||] ;;
dicho 0 [|0|] ;;
dicho 0 [|1|] ;;
dicho 0 [|1 ; 2|] ;;
dicho 0 [|0 ; 2|] ;;
dicho 0 [|-1 ; 0|] ;;
dicho 0 [|-2 ; -1|] ;;
for i = -1 to 17 do
    print_int i ;
    if dicho i [|0; 2; 4; 6; 8; 10; 12; 14; 16|] then print_string " Présent" else print_string " Absent" ; print_newline () done  ;;

(* Version rendue de complexité logarithmique par travail sur des indices plutôt que par extraction des sous-tableau *)
let dicho e t =
  let rec dicho_aux deb fin = 
    let n = fin + 1 - deb in
    if n = 0 then false
    else if n = 1 then t.(deb) = e
    else let m = deb + n / 2 in
         if t.(m) = e then true
         else if t.(m) > e then dicho_aux deb (m - 1)
         else dicho_aux (m + 1) fin          
  in dicho_aux 0 (Array.length t - 1) ;;

dicho 0 [||] ;;
dicho 0 [|0|] ;;
dicho 0 [|1|] ;;
dicho 0 [|1 ; 2|] ;;
dicho 0 [|0 ; 2|] ;;
dicho 0 [|-1 ; 0|] ;;
dicho 0 [|-2 ; -1|] ;;
for i = -1 to 17 do
    print_int i ;
    if dicho i [|0; 2; 4; 6; 8; 10; 12; 14; 16|] then print_string " Présent" else print_string " Absent" ; print_newline () done  ;;