// 斐波那契查找.cpp 

#include "stdafx.h"
#include <memory>
#include  <iostream>
using namespace std;

const int max_size=20;//斐波那契数组的长度

/*构造一个斐波那契数组*/ 
void Fibonacci(int * F)
{
    F[0]=0;
    F[1]=1;
    for(int i=2;i<max_size;++i)
        F[i]=F[i-1]+F[i-2];
}

/*定义斐波那契查找法*/  
int Fibonacci_Search(int *a, int n, int key)  //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
{
  int low=0;
  int high=n-1;
  
  int F[max_size];
  Fibonacci(F);//构造一个斐波那契数组F 

  int k=0;
  while(n>F[k]-1)//计算n位于斐波那契数列的位置
      ++k;

  int  * temp;//将数组a扩展到F[k]-1的长度
  temp=new int [F[k]-1];
  memcpy(temp,a,n*sizeof(int));

  for(int i=n;i<F[k]-1;++i)
     temp[i]=a[n-1];
  
  while(low<=high)
  {
    int mid=low+F[k-1]-1;
    if(key<temp[mid])
    {
      high=mid-1;
      k-=1;
    }
    else if(key>temp[mid])
    {
     low=mid+1;
     k-=2;
    }
    else
    {
       if(mid<n)
           return mid; //若相等则说明mid即为查找到的位置
       else
           return n-1; //若mid>=n则说明是扩展的数值,返回n-1
    }
  }  
  delete [] temp;
  return -1;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int a[] = {0,16,24,35,47,59,62,73,88,99};
    int key=100;
    int index=Fibonacci_Search(a,sizeof(a)/sizeof(int),key);
    cout<<key<<" is located at:"<<index;
    system("PAUSE");
    return 0;
}

3、代码解析

解析：
首先要明确：如果一个有序表的元素个数为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。

4、程序分析

1、程序开始执行，参数为 a = {0,1,16,24,35,47,59,62,73,88,99},n = 10,查找关键字为key = 59.根据事先生成的斐波那契序列，计算n在序列中位置，我们得到 F[6]<n<F[7]，所以k =7.

2、F[7] = 13，所以a[11]=a[12] = a[10] = 99.

3、查找开始，mid = 1+ F[6]-1 = 8，也就是说从下标8开始。此时a[8] =73>key =59,所以在左边，high = mid-1 = 7,k = k-1 =6;

4、再次循环，mid = 1+F[k-1] -1 = 5.此时从a[5] = 47<key开始查找，low = mid +1 = 6，k = 6-2 = 4.继而继续循环。

五、分块查找

分块查找又称索引查找。它是一种介于顺序查找和二分查找之间的查找方法。在分块查找中，主要求索引表是有序的，对块内结点没有排序要求，因此特别适合结点动态变化的情况。

1、存储结构

分块查找是由“分块有序”的线性表和索引表两部分构成。

分块有序的线性表：

假设要排序的表为R[0...N-1]，将表均匀分成b块，前b-1块中记录个数为s=N/b，最后一块记录数小于等于s；

每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字。

注：这是使用分块查找的前提条件。

如上将表均匀分成b块后，抽取各块中的最大关键字和起始位置构成一个索引表IDX[0...b-1]。

由于表R是分块有序的，所以索引表是一个递增有序表。

所示为一个索引顺序表。其中包括三个块，第一个块的起始地址为 0，块内最大关键字为 25；第二个块的起始地址为 5，块内最大关键字为 58，最小关键字为28，大于25；第三个块的起始地址为10，块内最大关键字为 88。

2、算法

分块查找算法有两个处理步骤：

(1) 首先查找索引表

因为分块查找表是“分块有序”的，所以我们可以通过索引表来锁定关键字所在的区间。

又因为索引表是递增有序的，所以查找索引可以使用顺序查找或二分查找。

(2) 然后在已确定的块中进行顺序查找

因为块中不一定是有序的，所以只能使用顺序查找。

3、代码

// 建立索引方法，n 是线性表最大长度，gap是分块的最大长度
    public IndexType[] createIndex(int list[], int n, int gap) {
        int i = 0, j = 0, max = 0;
        int num = n / gap;
        IndexType idxGroup[] = new IndexType[num]; // 根据步长数分配索引数组大小

        while (i < num) {
            j = 0;
            idxGroup[i] = new IndexType();
            idxGroup[i].link = gap * i; // 确定当前索引组的第一个元素位置
            max = list[gap * i]; // 每次假设当前组的第一个数为最大值
            // 遍历这个分块，找到最大值
            while (j < gap) {
                if (max < list[gap * i + j]) {
                    max = list[gap * i + j];
                }
                j++;
            }
            idxGroup[i].key = max;
            i++;
        }

        return idxGroup;
    }

    // 分块查找算法
    public int blockSearch(IndexType[] idxGroup, int m, int[] list, int n, int key) {
        int mid = 0;
        int low = 0;
        int high = m -1;
        int gap = n / m; // 分块大小等于线性表长度除以组数
        
        // 先在索引表中进行二分查找，找到的位置存放在 low 中
        while (low <= high) {
            mid = (low + high) / 2;
            if (idxGroup[mid].key >= key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        // 在索引表中查找成功后，再在线性表的指定块中进行顺序查找
        if (low < m) {
            for (int i = idxGroup[low].link; i < idxGroup[low].link + gap; i++) {
                if (list[i] == key)
                    return i;
            }
        }

        return -1;
    }

View Code

六、三种线性查找的PK

---

(1) 以平均查找长度而言，二分查找 > 分块查找 > 顺序查找。

(2) 从适用性而言，顺序查找无限制条件，二分查找仅适用于有序表，分块查找要求“分块有序”。

(3) 从存储结构而言，顺序查找和分块查找既可用于顺序表也可用于链表；而二分查找只适用于顺序表。

(4) 分块查找综合了顺序查找和二分查找的优点，既可以较为快速，也能使用动态变化的要求。

优质内容筛选与推荐>>
1、SelectClipRgn
2、前端优化之图片优化自动化[转]
3、IntelliJ IDEA 2017版 编译器使用学习笔记(一) (图文详尽版);IDE快捷键使用;IDE多行代码同时编写
4、安卓高手之路之java层Binder
5、构建之法03

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

好看

已推荐到看一看

你的朋友可以在“发现”-“看一看”看到你认为好看的文章。

取消 推荐

我知道了

已取消，“好看”想法已同步删除

知道了