Fibonacci Search

Fibonacci Search is a searching technique, where key position is found by using fibonacci list. In this technique two lists are used  one is input list and one is fibonacci list. For this search input list should contain numbers in ascending order.

Source Code:

def fibonacii(a,key):
    fib=[0,1,1,2,3,5,8,13]
    k=len(a)
    begin=0
    while k>0:
        k=k-1
        pos = begin+fib[k]
        if key == a[pos]:
            return pos
        elif key<a[pos]:
            continue
        else:
            begin=pos+1
            k=k-3
    return -1
a=[]
n=int(input("how many elements u want to enter"))
for i in range(n):
    a.append(int(input()))
key=int(input("enter the key"))
p=fibonacii(a,key)
if p==-1:
    print("%d not found" %key)
else:

    print("%d is found" %key)

Output:

how many elements u want to enter5

1

2

3

4

5

enter the key1

1 is found

>>> ================================ RESTART 

how many elements u want to enter5

1

2

3

4

5

enter the key3

3 is found

>>> ================================ RESTART  

how many elements u want to enter5

1

2

3

4

5

enter the key5

5 is found

>>> ================================ RESTART  

how many elements u want to enter5

1

2

3

4

5

enter the key100

100 not found

>>>