# 費氏搜尋法(Fibonacci Search)

和前面提到的二元搜尋和插值搜尋法類似，改變了中間節點 mid 的位置，mid不再是中間或插值得到，而是位於黃金分割點附近，搜尋時間為O(logn)。

## 基本介紹
大家應該都聽過費氏數列
`{1, 1, 2, 3, 5, 8, 13, 21, 34, 55}`

2 = 1 + 1
3 = 2 + 1
5 = 3 + 2
8 = 5 + 3
...

費氏數列的兩個相鄰數的比例無限接近黃金比例 `0.618`

費氏搜尋法就是利用這個特性設計的。

*用小算盤計算一下相鄰兩個值的比例都接近 `0.618`：


## 原理說明

和前面提到的二元搜尋和插值搜尋法類似，也是一樣改變了中間節點 mid 的位置，mid不再是中間或插值得到，而是位於黃金分割點附近，即 `mid = left + F[k-1] - 1` (F代表費氏數列)

* F[k] = F[k-1] + F[k-2]
* F[k-1] = (F[k-1] - 1) + (F[k-2] - 1) + 1
* k = 黃金分割點

但順序表長度 n 不一定剛好等於 `F[k]-1`，所以需要將原來的順序表長度 n 增加至 `F[k]-1`。這裡的k值只要能使得 `F[k]-1` 恰好大於或等於 n 即可，由以下代碼得到，順序表長度增加後，新增的位置(從 n+1 到 `F[k]-1` 位置)，都賦為 n 位置的值即可。

while(n>fib(k)-1) k++;

## 程式碼實現

package Search;

import java.util.Arrays;

public class FibSearch {
    static int maxSize = 20;
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        System.out.println("index = "+fibSearch(arr, 1));
        System.out.println("index = "+fibSearch(arr, 8));
        System.out.println("index = "+fibSearch(arr, 1000));
        System.out.println("index = "+fibSearch(arr, 555));
    }
    // 非遞迴方式得到一個費氏數列
    public static int[] fib() {
        int[] fib = new int[maxSize];
        fib[0] = 1;
        fib[1] = 1;
        for(int i = 2; i < maxSize; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib;
    }

    /**
     * 非遞迴方式寫費氏搜尋
     * @param arr 陣列
     * @param key 需要搜尋的值
     * @return 返回對應的索引, 如果沒有則返回 -1
     */
    public static int fibSearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int k = 0; // 表示費氏分割數值的索引, 也就是 k
        int mid = 0;
        int f[] = fib(); // 獲取費氏數列
        // 獲取費氏分割數值的索引
        while(high > f[k] - 1) {
            k++;
        }
        // 因為f[k] 值可能大於 arr 的長度, 因此需要構建一個新的陣列指向arr
        int[] temp = Arrays.copyOf(arr, f[k]);
        // 使用 arr 最後的數填充temp
        // {1, 8, 10, 89, 1000, 1234, 0, 0, 0...} => {1, 8, 10, 89, 1000, 1234, 1234, 1234, 1234...}
        for(int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        // 使用while來循環處理, 找到 key
        while(low <= high) {
            mid = low + f[k-1] - 1;
            if(key < temp[mid]) { // 應該繼續向左尋找
                high = mid - 1;
                k--;
            } else if (key > temp[mid]) {
                low = mid + 1;
                k -= 2;
            } else { // 找到
                if(mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}

output

index = 0
index = 1 
index = 4 
index = -1