Recherche séquentielle

Exercice · OCaml (option informatique), chapitre 10 — Recherche et dichotomie

É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;
  !trouve

Coût $Θ (n)$ au pire (parcours complet). On s'arrête dès qu'on a trouvé grâce à la condition !trouve = None.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.