бинарный поиск в OCaml?

Question

может кто-нибудь сказать мне, где ошибка здесь?

let a = [|2;4;6;9;12|];; 

a.(0);; 
a.(4);; 
a.(5);; 

let binary_search array size x = 
    let n = size-1 in 
    let p = ref 0 in 
    let r = ref n in 
    while (!p <= !r) do 
    let q = (!p + !r)/2;   
    if array.(q) = x 
    then raise ((Found_It (q));)      
    else if (array.(q) <> x) && (array.(q) > x) 
    then (r := q - 1;)    
    else if array.(q) < x 
    then (p := q + 1;) 
    done; 
    else -1;; 

exception Found_It of int;; 

, и если у вас есть предложения по бинарному поиску в ocaml, пожалуйста, сообщите мне?

Answer 1

Ваша проблема в том, что вы используете исключение, прежде чем оно будет определено в первую очередь. Переместите линию exception Found_It ... над линией let binary_search ....

Кроме того, как сказал Дрю, ваша проблема не имеет абсолютно никакого отношения к Emacs.

Answer 2

исключение Found_It of int ;; (* Здесь мы объявляем «исключение». Это специальный инструмент, который позволит нам сломать петлю. ) ( Данный исключения принимает целое число в качестве аргумента. *)

пусть binary_search размера массива х = пусть п = размер-1 (* пусть неизменяемую переменную п хранить конечный индекс массива ) пусть P = исх 0 в ( пусть minpoint д равен 0 ) пусть R = исх п в ( пусть максимальное значение r равно n *)

while !p <= !r do  
    let q = ref ((!p + !r)/2) in    (* calculate the midpoint for roughly equal partition *) 
    print_int !q; print_string " "; 
    if array.(!q) = x    (* if x is found at index p *) 
    then raise (Found_It (!q))  (* then break the loop with Found_It, which "carries" the value of q with it *)   
    else if array.(!q) > x   (* otherwise if q <> x and q > x *) 
    then r := !q - 1     (*change r index to search lower subarray*) 
    else p := !q + 1     (* otherwise if q < x change p index to search upper lower subarra *) 
done;        (* that's the end of the loop            *) 
-1; 

         (* so if we reach the end of the loop, output -1 for "Not found"    *) 

с Found_It (x) -> x ;; (* если мы сломали петлю с q, выход q *)