Prépa Code Connexion Inscription

Écrire une fonction recherche : int array -> int -> int qui prend un tableau t trié par ordre croissant et un entier x, et renvoie un indice i tel que t.(i) = x s'il existe, ou -1 sinon.

On attend une complexité en O(log n) (recherche dichotomique).

Comme on ne peut pas couper un tableau OCaml en deux moitiés sans le copier, on pourra définir une fonction auxiliaire :

let rec cherche t a b x = ...

qui effectue la recherche entre les indices a (inclus) et b (exclus) du tableau t, et appeler cherche t 0 (Array.length t) x depuis recherche.