arrays - 如果当前索引的值小于我们要查找的值，为什么我们在斐波那契搜索中丢弃 2 个斐波那契数？

Question

我有执行 Fibonacci 搜索的代码，我想知道如果我们的键大于数组中当前索引处的值，为什么我们要丢弃 2 个 Fibonacci 数？

public class FibSearch{
    static int fibSearch(int[] a, int x){
        int f1 = 1, f2 = 0, mid = 2;
        while(f1 < a.length){
            f1 = f1 + f2;
            f2 = f1 - f2;
            mid++;
        }

        int first = 0;
        mid--;
        f2 = f1 - f2;
        f1 = f1 - f2;

        while(mid > 0){
            int index = first + f1;
            if(index >= a.length || a[index] > x){
                mid--;
                f2 = f1 - f2;
                f1 = f1 - f2;
            }
            else if(a[index] == x){
                return index;
            }
            else{
                first = index;
                mid = mid - 2;
                f1 = f1 - f2;
                f2 = f2 - f1;
                //why not write
                //mid = mid - 1;
                //f2 = f1 - f2;
                //f1 = f1 - f2;
            }
        }
        return -1;
    }
}

如果我在说什么，最后一个 else 语句。

Answer 1

因为如果我们有一个斐波那契数列:0,1,1,2,3,5,8,13,... F(k - 1) + F(k - 3) 是落在中间的数F(k - 1) 和 F(k)，这就是我们想要的，因为它是分而治之的。