Fibonacci Search Algorithm in Python

.This post deals with the Fibonacci search algorithm. It is quite similar to the binary search algorithm. It operates on sorted arrays. However, it partitions the array into unequal sizes in contrast to the binary search technique.

Prerequisites: Basics of python lists

Fibonacci Search Algorithm

The basic idea behind the algorithm is to find the smallest Fibonacci number greater than or equal to the length of the array. Let’s say that is the i-th Fibonacci number stored as ‘fn’.

We then take up (i-2)the Fibonacci number and check whether the required element is at that index, if not we proceed as in binary search. That is, we check if it is greater or smaller than the required number. If smaller, we decrement the Fibonacci numbers to (i-3)th and (i-1)th i.e. by 1. This indicates that we have eliminated approximately the first 1/3rd of the array. Moreover, we also keep an ‘elim’ factor (initialized as -1) which keeps track of the elements eliminated (all elements from 0 to elim are eliminated). Hence we will also set elim to this checked index value. If the checked index was greater than the element we are looking for, that’s even better as we have eliminated approximately the last 2/3rd of the array and we decrement the Fibonacci numbers by 2 in this case and the elim value remains unchanged.

This process is repeated as long as fn remains greater than  1. That’s because, when fn is 1, fn_2 becomes 0 or doesn’t exist (becomes -ve). If the element is not found at the termination of the loop, the element is not present in the array.

Implementation using Python

Consider the following program for the implementation,

def fibonacci_search(arr,x):
    l = len(arr)
    elim = -1
    fn_2 = 0    #Two finbonacci numbers before fn
    fn_1 = 1    #One finonacci numbers before fn
    fn = fn_1+fn_2

    while fn<l:
        fn_1, fn_2 = fn, fn_1
        fn = fn_1+fn_2

    while fn>1:
        #Note: Searching after the 'elim' factor
        curr = min(elim+fn_2,l-1)  #To ensure index is within range

        if arr[curr] == x:
            return curr     #Returning the found index
        elif arr[curr] > x:   #Then element is first 1/3rd
            fn = fn_2
            fn_1 = fn_1 - fn_2
            fn_2 = fn_2 - fn_1   #Moving two down
        else:   #arr[curr] < x
            fn = fn_1
            fn_1 = fn_2
            fn_2 = fn - fn_1   #Moving 1 down
            elim = curr   #eliminating upto curr from 0 index
    return -1

In the output below, the search takes about 1.7 seconds to find the last element in an array having 10^7 elements

Why Fibonacci Search?

This search method proves to be useful, particularly in cases where the element is in the first 1/3rd of the division, in any of the early iterations. If it is always in the last 2/3rd, then it is a little slower than binary search. Hence, this has a case-specific advantage. Note, however, that the element doesn’t need to be in the first 1/3rd in the first iteration itself. That would mean the element is at the beginning of the array and even linear search can narrow it down in a short time! If the element is in the first 1/3rd at least in the first few iterations, the algorithm is faster than binary search.

Moreover, we are using the Fibonacci series since as the series progresses, the ration of consecutive numbers approaches the golden ratio 1.618…,  hence it divides the array also in the same ratio.

And just to add a fact, the Fibonacci search does all the index calculations by using just addition or subtraction. Whereas, binary search uses division and multiplication. That used to be a harder process in the early years of the computing world. Hence, it was a more preferred method when it was introduced. Now, the difference may not be that pronounced.

Feel free to leave behind any sort of feedback, suggestions, doubts, below.