是对折半查找达的改进
利用黄金分割点进行数据的分析（将数组分为两半，一长一短，如果要查找的数分布在短的这一部分，那么它的效率就会大大提高，反之，则效率低于折半查找。所以它的效率不一定高于折半查找）。
有必要提一下，斐波那契数列的规律：前两项是1，从第三项开始，每一项都是前两个数之和。
以下附上图和代码，需要注意点在代码中都有注释
#include <stdio.h> int fib[10] = { 1,1,2,3,5,8,13,21,34,55 }; int fibSearch(int a[], int n, int key) { int low = 0; int high = n - 1; int k = 0; while (n > fib[k] - 1)//找到数组长度n在斐波那契数组里边的位置 k++; for (int i = n; i < fib[k] - 1; i++)//使得；数组a后边的元素都等于a[n-1] { a[i] = a[n-1];//a[i]表示数组a后边的元素即a[10]，然而根据图示可以看出此位置已经被占用，所以，数组长度需要增加 } int mid;//利用折半查找中间值的思想 while (low <= high) { mid = low + fib[k - 1] - 1; if (a[mid] == key) { if (mid < n) return mid; else return n - 1; } else if (a[mid] < key) { low = mid + 1; k = k - 2; } else { high = mid - 1; k = k - 1; } } return -1; } int main() { int a[13] = { 7,18,23,39,45,55,62,71,84,98 };//此处数组长度需要是斐波那契数组里边的值 int index = fibSearch(a, 10, 23); return 0; }