Fibonacci Search using Python | Data Structure and Algorithms

 Code:

Note:- Scroll horizontally to see the full line of code.

def fibonacci_search(a,target):

    # a is list of intergers and target is key element to be searched

    n=len(a)

    fibn_2=0

    fibn_1=1

    fibn=fibn_1+fibn_2

    while(fibn<=n):

        fibn_2=fibn_1

        fibn_1=fibn

        fibn=fibn_1+fibn_2

    offset=-1

    while(fibn_1!=0):

        i=min((offset+fibn_2),n-1)

        if(target>a[i]):

            fibn=fibn_1

            fibn_1=fibn_2

            fibn_2=fibn-fibn_1

            offset=i

        elif(target<a[i]):

            fibn=fibn_2

            fibn_1=fibn_1-fibn_2

            fibn_2=fibn-fibn_1

        elif(target==a[i]):

            print(target,"is present at index",i)

            break

    else:

        print(target,"not found in list")