【愚公系列】2021年11月 C#版 数据结构与算法解析(斐波那契查找)

斐波那契查找是区间中单峰函数的搜索技术，它在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于或略大于查找表中元素个数的数F[n]，如果原查找表长度不足F[n]，则补充重复最后一个元素，直到满足F[n]个元素时为止。完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，根据值的关系确定往前或往后查找，直到找到时为止。如果一直找不到，则返回-1。

示例：

public class Program {
 
    public static void Main(string[] args) {
        int[] array = { 8, 11, 21, 28, 32, 43, 48, 56, 69, 72, 80, 94 };
        CalculateFibonacci();
 
        Console.WriteLine(FibonacciSearch(array, 80));
 
        Console.ReadKey();
    }
 
    private const int MAXSIZE = 47;
 
    private static int[] _fibonacciArray = new int[MAXSIZE];
 
    private static void CalculateFibonacci() {
        _fibonacciArray[0] = 1;
        _fibonacciArray[1] = 1;
        //计算斐波那契数，使用数组保存中间结防止重复计算，
        //注意MAXSIZE为48时，斐波那契数将会溢出整型范围。
        //1,1,2,3,5,8,13,21,34,55,89...
        for(int i = 2; i < _fibonacciArray.Length; i++)
            _fibonacciArray[i] = _fibonacciArray[i - 1] + _fibonacciArray[i - 2];
    }
 
    private static int FibonacciSearch(int[] array, int key) {
        int length = array.Length;
        int low = 0, high = length - 1, mid, k = 0;
 
        //先查找到距离最近的斐波那契数，本案例为k=6时，值13
        int[] banlance;
        while(length > _fibonacciArray[k])
            k++;
 
        //数组的数量必须为_fibonacciArray[k]，所以使用一个中间平衡数组
        if(length < _fibonacciArray[k]) {
            banlance = new int[_fibonacciArray[k]];
            for(int i = 0; i <= length - 1; i++)
                banlance[i] = array[i];
        } else {
            banlance = array;
        }
 
        //平衡数组中的后半部分用前面的最后一个值补全
        for(int i = length; i < _fibonacciArray[k]; i++)
            banlance[i] = banlance[length - 1];
 
        //接下来的过程和二分查找类似
        while(low <= high) {
            mid = low + _fibonacciArray[k - 1] - 1;
            if(banlance[mid] > key) {
                high = mid - 1;
                k--;
            } else if(banlance[mid] < key) {
                low = mid + 1;
                k -= 2;
            } else {
                //防止索引出界
                if(mid <= length - 1)
                    return mid;
                return length - 1;
            }
        }
 
        //查找不到时返回-1
        return -1;
    }
 
}

在最坏的情况下斐波那契查找的时间复杂度为：O(logn) 。