斐波那契查找是区间中单峰函数的搜索技术，它在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于或略大于查找表中元素个数的数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) 。
