⬅ Fibonacci Search (Ascending) | A Helpful Line-by-Line Code Tutorial | Search Algorithm

# [0, 1, 1, 2, 3, 5, 8, 13...]

# return the fibonacci number at the index of n
def FibonacciGenerator(n):
    if n < 1:
        return 0
    elif n == 1:
        return 1
    else:
        return FibonacciGenerator(n - 1) + FibonacciGenerator(n - 2)

# return the index at which x exists inside arr
# return -1 otherwise

def FibonacciSearch(arr, x):

    # find the smallest Fibonacci number greater than or equal
    # to the length of arr
    m = 0 
    while FibonacciGenerator(m) < len(arr): # 
        m = m + 1 

    # [10, 22, 30, 44, 56, 58, 60, 70, 100, 110, 130] 
    # m = 7

    # m now contains the index of the the smallest Fibonacci
    # number greater than or equal to the length of the array
    # for example
    # if the length of arr is 11, FibonacciGenerator(m) should be 13

    # this is the length of that array from the
    # start that has been eliminated
    offset = -1

    # [10, 22, 30, 44, 56, 58, 60, 70, 100, 110, 130] 
    # m = 7
    # offset = -1

    # make sure you fibonacci index is valid
    while (FibonacciGenerator(m) > 1):

        i = min( offset + FibonacciGenerator(m - 2) , len(arr) - 1)

        # [10, 22, 30, 44, 56, 58, 60, 70, 100, 110, 130] 
        # m = 3
        # offset = 5
        # i = 6
        # x = 60

        if (x > arr[i]):

            m = m - 1
            offset = i

        elif (x < arr[i]):

            m = m - 2

        else:

            return i

    # this will run if there is one last element left
    if(FibonacciGenerator(m - 1) and arr[offset + 1] == x):
        return offset + 1

    # return -1 if the element doesn't exist in the array
    return -1


# the search array
arr = [10, 22, 30, 44, 56, 58, 60, 70, 100, 110, 130] 
x = 60
print(FibonacciSearch(arr, x))