this is pure python implementation of fibonacci search resources used https en wikipedia orgwikifibonaccisearchtechnique for doctests run following command python3 m doctest v fibonaccisearch py for manual testing run python3 fibonaccisearch py finds fibonacci number in index k parameters k index of fibonacci returns int fibonacci number in position k fibonacci0 0 fibonacci2 1 fibonacci5 5 fibonacci15 610 fibonacci a traceback most recent call last typeerror k must be an integer fibonacci5 traceback most recent call last valueerror k integer must be greater or equal to zero a pure python implementation of a fibonacci search algorithm parameters arr list of sorted elements val element to search in list returns int the index of the element in the array 1 if the element is not found fibonaccisearch4 5 6 7 4 0 fibonaccisearch4 5 6 7 10 1 fibonaccisearch18 2 18 0 fibonaccisearch5 5 0 fibonaccisearch a c d c 1 fibonaccisearch a c d f 1 fibonaccisearch 1 1 fibonaccisearch 1 4 7 4 1 fibonaccisearch 9 1 fibonaccisearchlistrange100 63 63 fibonaccisearchlistrange100 99 99 fibonaccisearchlistrange100 100 3 97 1 fibonaccisearchlistrange100 100 3 0 1 fibonaccisearchlistrange100 100 5 0 20 fibonaccisearchlistrange100 100 5 95 39 find m such that fm n where fi is the ith fibonacci number finds fibonacci number in index k parameters k index of fibonacci returns int fibonacci number in position k fibonacci 0 0 fibonacci 2 1 fibonacci 5 5 fibonacci 15 610 fibonacci a traceback most recent call last typeerror k must be an integer fibonacci 5 traceback most recent call last valueerror k integer must be greater or equal to zero a pure python implementation of a fibonacci search algorithm parameters arr list of sorted elements val element to search in list returns int the index of the element in the array 1 if the element is not found fibonacci_search 4 5 6 7 4 0 fibonacci_search 4 5 6 7 10 1 fibonacci_search 18 2 18 0 fibonacci_search 5 5 0 fibonacci_search a c d c 1 fibonacci_search a c d f 1 fibonacci_search 1 1 fibonacci_search 1 4 7 4 1 fibonacci_search 9 1 fibonacci_search list range 100 63 63 fibonacci_search list range 100 99 99 fibonacci_search list range 100 100 3 97 1 fibonacci_search list range 100 100 3 0 1 fibonacci_search list range 100 100 5 0 20 fibonacci_search list range 100 100 5 95 39 find m such that f_m n where f_i is the i_th fibonacci number prevent out of range
from functools import lru_cache


@lru_cache
def fibonacci(k: int) -> int:
    
    if not isinstance(k, int):
        raise TypeError("k must be an integer.")
    if k < 0:
        raise ValueError("k integer must be greater or equal to zero.")
    if k == 0:
        return 0
    elif k == 1:
        return 1
    else:
        return fibonacci(k - 1) + fibonacci(k - 2)


def fibonacci_search(arr: list, val: int) -> int:
    
    len_list = len(arr)
    
    i = 0
    while True:
        if fibonacci(i) >= len_list:
            fibb_k = i
            break
        i += 1
    offset = 0
    while fibb_k > 0:
        index_k = min(
            offset + fibonacci(fibb_k - 1), len_list - 1
        )  
        item_k_1 = arr[index_k]
        if item_k_1 == val:
            return index_k
        elif val < item_k_1:
            fibb_k -= 1
        elif val > item_k_1:
            offset += fibonacci(fibb_k - 1)
            fibb_k -= 2
    else:
        return -1


if __name__ == "__main__":
    import doctest

    doctest.testmod()