演算法知識 - 費氏搜尋 Fibonacci Search

費氏搜尋 Fibonacci Search 介紹與實作原理

主要是透過費氏數列所組成的費氏二元樹來對數列進行搜尋，主要的搜尋方式與二元搜尋大概相同，不同之處在於費氏二元樹與二分搜尋的二元樹構造不同。

費氏二元樹在往左右子樹時，只需要使用加減法，不使用乘或除法。
有些 CPU 在乘除法的運算來的過大。

費氏二元樹，我們透過此圖進行理解

• 有一個數列長度有 33，裡面的數字從 1~33，
• 我們必須先建立一顆費氏二元樹，我們先透過費氏數列找出 \(f(n) >= 33\)，其中 \(n = 8\)
• \(fib(8) = 35\)，其實我們可以發現 \(fib(8) = fib(7) + fib(6) \)，其實可以看的出來一些端倪，\(root = 左子樹、右子樹\)，因此 \(fib(8)\) 就是這邊的 root、\(fib(7)\) 是左子樹、\(fib(6)\) 是右子樹
• 左子樹的樹值一定比 root 小，右子樹的數值一定比 root 大
• 其實費氏樹與二元樹相同，只是二元樹是左右子樹的葉節點一樣大，而費氏樹的左子樹葉節點數量有 \(fib(n-1)\)、費氏樹的右子樹葉節點數量有 \(fib(n-2)\)。
• 再來我們就是不斷地用加減法來算出下個子樹的 index。
• 需要記住費氏數列的 index 從 0 開始。
  
  [search] fibonacci search by Chris Yang 學習筆記，如果作者不願意圖片供我引用，請告訴我，我會馬上刪除，讓你感到不舒服我很抱歉QQ

定義 value: 為我們要查詢的樹值
那我們主要就是從 root 開始找

• 如果 root == value，退出 search
• 如果 value > root 往右子樹找
• 如果 value < root 往左子樹找

費氏搜尋 Fibonacci Search 程式碼說明與應用

透過程式碼來進行說明相信會更好理解，以下我們示範搜尋 4 這個位置。

由於我們資料離散程度相當，因此只需要一次我們就可以成功找到。

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
int num[] = {1,2,3,4,5,6,7,8,9,10}; //已經排序好的數列 
int num_size; //數列長度

int fib(int i){ //費式數列
    if(i == 1 || i == 0) return i;
    return fib(i-1) + fib(i-2);
}

int fib_search(int val){ //費氏搜尋
    cout << "fib search start.\n";

    int i = 2, cnt=0;
    num_size--; //我們實際的 index 最大只到 9，但長度有 10
    while(num_size > fib(i)) i++; //找出 fib(i) >= num_size

    i--; //折半找出 root
    int root = fib(i); //root 
    int diff1 = fib(i-1); //fib(root-1) 
    int diff2 = fib(i-2); //fib(root-2) 我們會透過 diff1 and diff2 來找出左右子樹位置。
    root--; //由於我們 index 從 0 開始，因此 root-1

    //    ^ ^
    //1 1 3 5 8 13 22 35 
    while(1){
        cout << "root " << root << '\n';
        cout << ++cnt << " search. find " << num[root] << '\n';

        if(val == num[root]) return root; //找到 val 的位置，輸出 index
        if(val < num[root]){ //往左子樹的方向找
            //我們主要透過此方式來推出左子樹位置
            //fib(n) = fib(n-1) + fib(n-2)，假設這三個數我們都已知
            //fib(n-1) = fib(n-2) + fib(n-3)，由於我們知道 fib(n-1) 與 fib(n-2)，就可以求出 fib(n-3)

            root -= diff2; //往左子樹的 root(index) 找
            int temp = diff1; //temp = fib(n-1)
            diff1 = diff2; //diff1 = fib(n-2)
            diff2 = temp - diff2; //fib(n-3) = fib(n-1) - fib(n-2)，分別對應左邊 3 個變數
            i--; //fib 的數列降低一層，因為左子樹的數量是 fib(n-1)
        }
        if(val > num[root]){
            root += diff2; //往右子樹的 root(index) 找
            diff1 = diff1 - diff2; //fib(n-3) = fib(n-1) - fib(n-2)，分別對應左邊 3 個
            diff2 = diff2 - diff1; //fib(n-4) = fib(n-2) - fib(n-3)，分別對應左邊 3 個
            i -= 2; //fib 的數列降低兩層，因為右子樹的數量是 fib(n-2)
        }
    }
    cout << "cat't find " << val << "\n";
    return -1; //無法找到，輸出 -1
}

int main()
{
    num_size = sizeof(num) / sizeof(num[0]);
    int val = 4;
    cout << val << " position is " << fib_search(val) << '\n';
    return 0;
}

參考連結

[search] fibonacci search by Chris Yang 學習筆記
Fibonacci Search by GeeksforGeeks

心得

高中之前就有學習過 fib serach，但學會後我就再也沒有去複習這些知識。

剛好現在上課有用到那就來複習，順便把它寫出邏輯八！

程式執行結果