在討論費氏搜尋之前，要先了解一下費氏數列。

費氏數列 (Fibonacci numbers)，又稱費波那契數列，是指在一串數字中，每一項是前兩項的和。數學上的定義為：

• 第 0 項 = 0
• 第 1 項 = 1
• 第 n 項 = 第 n-1 項 + 第 n-2 項

公式為：f(n) = f(n-1) + f(n-2), n >= 2

直接列出前十項，觀察一下就能了解了。

def fibonacci(n):
    if n == 0:
        return 0;
    elif n == 1:
        return 1;
    return fibonacci(n-1) + fibonacci(n-2)
    
print(fibonacci(7))

在大致了解費氏數列後，那費氏搜尋法又是如何運作呢？

假設我們要在已經排序好的數列中找到數字：
費氏數列 fib = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
查找資料 data = [10, 22, 30, 44, 56, 58, 60, 70, 100, 110, 130]
搜尋值 key = 60

1. 要事先算出費氏數列fib，費氏數列裡的值fib[i]會用來當作查找資料裡的索引值。
2. 用查找資料的長度大小 len(data) = 11，和費氏數列的值做比較，找到費氏數列裡的值 fib[6] = 8，最接近小於或等於查找資料的長度大小 y = 6，代表查找資料這棵樹的根節點編號，也是費氏數列的索引值。
3. 設定怎麼從查找資料跳著找。從資料索引的最大值減去 fib[y] = fib[6]，m = 10 - 8 = 2
4. 設定從費氏數列的第幾個索引開始找要給查找資料找數字的索引值。x = y - 1 = 5
5. 如果查找資料在索引 5 處的值大於指定的搜尋值，則第一個搜尋位置就是索引 5 的位置，如果小於指定的搜尋值，則第一個搜尋位置必須加上 m，也就是 fib[5] + m = 5 + 2 = 7，也就是索引 7 的位置，其實加上 m 的原因，是為了要讓下一個搜尋值剛好是數列的最後一個位置。

(真的要用不同的資料多試幾次，才會慢慢了解查找的概念...真的蠻繞的，但只要了解，會發現速度很快)

import sys

# 產生費氏數列
def fibo(max):
    fib = [sys.maxsize] * max
    fib[0] = 0
    fib[1] = 1
    for i in range(2, max):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib

def getY(fib, n):
    i = 0
    while fib[i] <= n:
        i += 1
    return i - 1

def search(data, key):
    fib = fibo(len(data))
    max = len(data) - 1  # data的最大索引值
    y = getY(fib, max + 1) # 在費氏數列裡的值，如果比data的最大索引值還大，回傳費氏數列索引值的前一個
    m = max - fib[y] 
    x = y - 1  #找到在data搜尋的起始索引值
    print("\nx=%d, m=%d, fib[x]=%d" % (x, m, fib[x]))
    i = x
    if data[i] < key:
        i += m
    while fib[x] > 0:
        if data[i] < key:
            x -= 1
            i += fib[x]
        elif data[i] > key:
            x -= 1
            i -= fib[x]
        else:
            return i
    return -1

number = [10, 22, 30, 44, 56, 58, 60, 70, 100, 110, 130]
find = search(number, 60)
print("找到數值於索引 " + str(find) if find >= 0 else "找不到數值")