# Fibonacci Search費氏搜尋
###### tags: `Algorithm` `Datastruction`
先了解費氏數列
再了解費氏樹
1. 保留費氏樹的節點關係，但先不看節點值，請把它當作是一個二元搜尋樹。
2. 其左邊子節點連接的所有值都必須要小於該節點的值
3. 其右邊子節點連接的所有值都必須要大於或等於該節點的值。
4. 二元搜尋樹任意節點與其左、右子節點的差之絕對值都是一樣的。

**歸納後我們知道的特性：**
* 費氏樹的左右子樹皆為費氏樹
* 父節點與子節點的相差值會等於某個費氏數值f(n)
* 左節點的數值會小於父節點
* 右節點的數值會大於等於父節點

先了解費氏數列及費事樹，就可以知道這段程式碼的運行邏輯，因為data已經sort好了，我們只需要負責search就好，而這種搜尋法的好處是只用到加減運算而不需用到乘法及除法，以電腦的運算方式效率應該不錯。

1. 程式從Rootnode開始跑
2. 下一個費氏數 diff1=fib(index-1)
3. 下兩個費氏數 diff2=RootNode-diff1

範例的費氏樹圖：

python code:

# -*- coding: utf-8 -*-
from __future__ import print_function

MAX=20

def fib(n):#生成費式函數
    if n==1 or n==0:
        return n
    else:
        return fib(n-1)+fib(n-2)
    
def fib_search(data,SearchKey):
    global MAX
    index=2
    #費氏數列的搜尋
    while fib(index)<=MAX :#f(a)>=n+1
        index+=1
    # index >=2
    #起始的費氏數
    index-=1
    RootNode=fib(index)#放入預先設定好的頭，f(index-1)，父節點才是中間最上面那個
    #上一個費氏數
    diff1=fib(index-1)
    #上二個費氏數即diff2=fib(index-2)
    diff2=RootNode-diff1
    RootNode-=1 #這列運算式是配合陣列的索引是從0開始儲存資料，陣列頭是data[0]=5
    while True:
        if SearchKey==data[RootNode]:
            return RootNode
        else:
            if index==2:#2為左費氏數的底層
                return MAX #沒有找到
            if SearchKey<data[RootNode]:
                RootNode=RootNode-diff2#左子樹的新費氏數
                temp=diff1
                diff1=diff2#上一個費氏數
                diff2=temp-diff2#上二個費氏數
                index=index-1
            else:
                if index==3:#3為左費氏數的底層
                    return MAX
                RootNode=RootNode+diff2#右子樹的新費氏數
                diff1=diff1-diff2#上一個費氏數
                diff2=diff2-diff1#上二個費氏數
                index=index-2
                

data=[5,7,12,23,25,37,48,54,68,77, \
      91,99,102,110,118,120,130,135,136,150]
i=0
j=0
while True:
    val=int(input('請輸入搜尋鍵值(1-150)，輸入-1結束：'))
    if val==-1: #輸入值為-1就跳離迴圈
        break
    RootNode=fib_search(data,val)#利用費氏搜尋法找尋資料
    if RootNode==MAX:
        print('##### 沒有找到[%3d] #####' %val)
    else:
        print('在第 %2d個位置找到 [%3d]' %(RootNode+1,data[RootNode]))
   
print('資料內容：')
for i in range(2):
    for j in range(10):
        print('%3d-%-3d' %(i*10+j+1,data[i*10+j]),end='')
    print()