OCaml (option informatique) · Chapitre 10 · Application directe du cours
Recherche séquentielle
Recherche et dichotomie · niveau 1 (application)
Énoncé
Écrire recherche x t renvoyant Some i (première position) ou None. Quel est son coût ?
Corrigé
let recherche x t =
let n = Array.length t in
let i = ref 0 and trouve = ref None in
while !i < n && !trouve = None do
if t.(!i) = x then trouve := Some !i;
i := !i + 1
done;
!trouveCoût au pire (parcours complet). On s'arrête dès qu'on a trouvé grâce à la condition !trouve = None.
Exercices semblables
- Racine carrée entière par dichotomie corrigé
- Recherche d'un seuil monotone corrigé
- Exponentiation modulaire rapide corrigé
- Recherche dichotomique corrigé
- Exponentiation rapide corrigé