斐波那契查找原理解析

刺骨的言语ヽ痛彻心扉 2022-03-15 16:46 287阅读 0赞

转载自[http://blog.chinaunix.net/uid-27164517-id-3313988.html][http_blog.chinaunix.net_uid-27164517-id-3313988.html]

--------------------

#include <iostream>
    #include <assert.h>
    
    #define MAXSIZE 13
    
    void Fibonacci(int *f)
    {
        f[0] = 1;
        f[1] = 1;
    
        for (int i = 2; i < MAXSIZE; i++)
        {
            f[i] = f[i - 1] + f[i - 2];
        }
    }
    
    int Fibonacci_Search(int *a, int n, int key)
    {
        int low, high, mid;
    
        low = 1;
        high = n - 1;
     
        int k = 0;
        int F[MAXSIZE];
        Fibonacci(F);
    
         //这个查找n在斐波那契数列中的位置，为什么是F[k] - 1,而不是F[k]？
        while ( n > F[k] - 1 )
        {
            k++;
        }
    
        //这个地方，我发现被查找的数组a的长度不好计算，比如，我现在要查找31在数组a中的位置
        //那么，由于n = 13， 位于斐波那契数列中的第7个数（21）和第8个数（34）之间，所以k的
        //值为7，F[k] - 1就等于20，那么数组a的长度就需要是a[20]。换个数又变了，我不知道这个
        //应该怎么控制？
        for (int i = n; i < F[k] - 1; i++)
        {
            a[i] = a[high];
        }
    
            //还有这个判断，当键值小于a[mid]时，就在[low, F[k - 1] - 1]范围内查找
            //当键值大于a[mid]时，就在[F[k - 2] - 1]范围内查找，这个依据是什么？
        while(low <= high)
        {
            mid = low + F[k - 1] - 1;
    
            if ( key < a[mid] )
            {
                high = mid - 1;
                k = k - 1;
            }
            else if ( key > a[mid] )
            {
                low = mid + 1;
                k = k - 2;
            }
            else
            {
                if ( mid <= high )
                {
                    return mid;
                }
                else
                    return n;
            }
        }
        return -1;
    }

解析：  
首先要明确：如果一个**有序表的元素个数为n**,**并且n正好是（某个斐波那契数 - 1），即n=F\[k\]-1时，才能用斐波那契查找法**。 如果有序表的元素个n不等于（某个斐波那契数 - 1），即n≠F\[k\]-1，这时必须要将有序表的元素扩展到大于n的那个斐波那契数 - 1才行，这段代码：  
for (int i = n; i < F\[k\] - 1; i++)  
\{  
a\[i\] = a\[high\];  
\}  
便是这个作用。  
  
下面回答  
第一个问题：看完上面所述应该知道①是为什么了吧。 查找n在斐波那契数列中的位置，为什么是F\[k\] - 1,而不是F\[k\]，是因为能否用斐波那契查找法是由F\[k\]-1决定的，而不是F\[k\]。如果暂时不理解，继续看下面。  
  
第 二个问题：a的长度其实很好估算，比如你定义了有10个元素的有序数组a\[20\]，n=10，那么n就位于8和13，即F\[6\]和F\[7\]之间，所以 k=7，此时数组a的元素个数要被扩充，为：F\[7\] - 1 = 12个； 再如你定义了一个b\[20\]，且b有12个元素，即n=12,那么很好办了，n = F\[7\]-1 = 12, 用不着扩充了； 又或者n=8或9或11，则它一定会被扩充到12； 再如你举的例子，n=13，最后得出n位于13和21，即F\[7\]和F\[8\]之间，此时k=8，那么F\[8\]-1 = 20,数组a就要有20个元素了。 所以，n = x（13<=x<=20）时，最后都要被扩充到20；类推，如果n=25呢，则数组a的元素个数肯定要被扩充到 34 - 1 = 33个（25位于21和34，即F\[8\]和F\[9\]之间，此时k=9，F\[9\]-1 = 33），所以，n = x（21<=x<=33）时，最后都要被扩充到33。也就是说，最后数组的元素个数一定是（某个斐波那契数 - 1），这就是一开始说的n与F\[k\]-1的关系。  
  
第三个问题:对于二分查找，分割是从mid= (low+high)/2开始；而对于斐波那契查找，分割是从mid = low + F\[k-1\] - 1开始的； 通过上面知道了，数组a现在的元素个数为F\[k\]-1个，即数组长为F\[k\]-1，mid把数组分成了左右两部分， 左边的长度为：F\[k-1\] - 1， 那么右边的长度就为（数组长-左边的长度-1）， 即：（F\[k\]-1） - （F\[k-1\] - 1） = F\[k\] - F\[k-1\] - 1 = F\[k-2\] - 1。  
斐波那契查找的核心是：  
1）当key=a\[mid\]时，查找成功；  
2）当key 3）当key>a\[mid\]时，新的查找范围是第mid+1个到第high个，此时范围个数为F\[k-2\] - 1个，即数组右边的长度，所以要在\[F\[k - 2\] - 1\]范围内查找。

[http_blog.chinaunix.net_uid-27164517-id-3313988.html]: http://blog.chinaunix.net/uid-27164517-id-3313988.html