def fibonacci_search(lis, key):

    #

    F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,

         233, 377, 610, 987, 1597, 2584, 4181, 6765,

         10946, 17711, 28657, 46368]

    low = 0

    high = len(lis) - 1

    #

    k = 0

    while high > F[k]-1:

        k += 1

    print(k)

    i = high

    while F[k]-1 > i:

        lis.append(lis[high])

        i += 1

    print(lis)

    #

    time = 0

    while low <= high:

        time += 1

        #

        if k < 2:

            mid = low

        else:

            mid = low + F[k-1]-1

        print("low=%s, mid=%s, high=%s" % (low, mid, high))

        if key < lis[mid]:

            high = mid - 1

            k -= 1

        elif key > lis[mid]:

            low = mid + 1

            k -= 2

        else:

            if mid <= high:

                #

                print("times: %s" % time)

                return mid

            else:

                print("times: %s" % time)

                return high

    print("times: %s" % time)

    return False

LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]

result = fibonacci_search(LIST, 444)

print(result)