Bisekcija/Implementacija Ocaml

Iz MaFiRaWiki

Funkcija sproži izjemo Not_found, če iskanega elementa ni v tabeli.

Rekurzivna rešitev

  1. let bisekcija a x =
  2. let rec bis i j =
  3. if i > j then
  4. raise Not_found
  5. else
  6. let k = (i + j)/2 in
  7. let c = compare a.(k) x in
  8. if c < 0 then bis (k+1) j
  9. else if c > 0 then bis i (k-1)
  10. else k
  11. in
  12. bis 0 (Array.length a - 1)

Rešitev z zanko

  1. exception Rezultat of int ;;
  2.  
  3. let bisekcija a x =
  4. try
  5. let i = ref 0 in
  6. let j = ref (Array.length a - 1) in
  7. while !i <= !j do
  8. let k = (!i + !j) / 2 in
  9. if a.(k) < x then i := k + 1
  10. else if a.(k) > x then j := k - 1
  11. else raise (Rezultat k)
  12. done ;
  13. raise Not_found
  14. with Rezultat k -> k ;;
Osebna orodja