CODE EXAMPLE FOR CPP

fibonacci search algorithm c++

FUNCTION FIBONACCI_SEARCH(ITEM: INTEGER; ARR: SORT_ARRAY) RETURN INDEX IS
    L : INDEX := ARR'FIRST; -- FIRST ELEMENT OF ARRAY
    U : INDEX := ARR'LAST; -- LAST ELEMENT OF ARRAY
    M : INDEX := (U+L)/2;
    X,A,B : INTEGER; 
BEGIN
    A := (FN-3);
    B := (FN-2)-(FN-3);  
    DISCRETE (F2,F1) := (FN-2,FN-3)
        NEW (F2,F1) := (F2-F1,2*F1-F2) | (A,B)
    WITH I := U-L+1
        NEW I=I/2 LOOP
    LOOP
        IF ITEM < ARR(M) THEN
            M := M-F1; -- COMPUTE NEW POSITION OF COMPARED ELEMENT 
            F2 := F2-F1;
            F1 := F1-F2;
        ELSIF ITEM > ARR(M) THEN
            M := M+F1; -- COMPUTE NEW POSITION OF COMPARED ELEMENT
            X := F1;
            F1 := F2-F1;
            F2 := X; 
            A := F2; B := F1;
        ELSE
            RETURN M; -- RETURN INDEX OF FOUND ITEM
        END IF;
        I := I/2; 
    END LOOP;
END FIBONACCI_SEARCH;