【愚公系列】2023年11月 七大查找算法(四)-斐波那契查找
🏆 作者简介，愚公搬代码 🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，阿里云专家博主，腾讯云优秀博主，掘金优秀博主，51CTO博客专家等。 🏆《近期荣誉》：2022年CSDN博客之星TOP2，2022年华为云十佳博主等。
🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。
🏆🎉欢迎 👍点赞✍评论⭐收藏
🚀前言
在编程语言中，查找算法是指在一个数据集合中查找某个元素是否存在的算法。常见的查找算法包括：
- 顺序查找（Sequential Search）：逐个遍历数据集来查找目标元素，时间复杂度为O(n)。
- 二分查找（Binary Search）：在有序数据集合中，从中间位置作为起点不断划分区间并查找，时间复杂度为O(log n)。
- 插值查找（Interpolation Search）：在有序数据集合中，根据目标元素与数据集合首尾之间的差值，利用插值估算目标元素的位置，时间复杂度为O(log log n)或O(n)。
- 斐波那契查找（Fibonacci Search）：在有序数据集合中，根据斐波那契数列调整中间点的位置来查找，时间复杂度为O(log n)。
- B树查找（B-Tree Search）：在平衡的B树中查找元素，时间复杂度为O(log n)。
- 哈希查找（Hash Search）：通过哈希函数将元素映射到哈希表中，并在哈希表中查找元素，时间复杂度为O(1)。
- 分块查找（Block Search）：将数据集合划分为若干块，在每个块中进行二分查找或顺序查找，时间复杂度为O(sqrt(n))。
以上算法都有各自适用的场景，开发者需要根据数据集合的特性和需求选择最适合的算法来进行查找。
🚀一、斐波那契查找
🔎1.基本思想
斐波那契查找算法的基本思想是将要查找的元素与斐波那契数列中的元素进行比较，并根据比较的结果确定下一步查找的范围。具体来说，算法首先在斐波那契数列中找到大于或等于要查找的元素的最小数（称为斐波那契数列的查找点），然后根据该查找点将数组分为两部分，一部分是查找点左侧的元素，另一部分是查找点右侧的元素。如果要查找的元素等于查找点处的元素，则查找成功；如果要查找的元素小于查找点处的元素，则在查找点左侧的元素中继续查找；如果要查找的元素大于查找点处的元素，则在查找点右侧的元素中继续查找。重复以上步骤，直到找到要查找的元素或者确定要查找的元素不在数组中。斐波那契查找算法的时间复杂度为O(log n)。
🔎2.复杂度分析
斐波那契查找算法的时间复杂度为O(log n)，空间复杂度为O(1)。
在斐波那契查找算法中，先使用斐波那契数列生成器生成斐波那契数列，选取一个在斐波那契数列中的值作为分割点，将原序列划分为两部分。然后根据要查找的值和分割点的值大小关系，将要查找的值所在的部分继续递归查找，直到找到要查找的值或者原序列中不存在该值为止。
由于斐波那契数列增长速度非常快，因此划分部分的次数相对较少，所以时间复杂度为O(log n)。
由于算法中只需要使用常数个变量和常数个函数调用栈，因此空间复杂度为O(1)。
🔎3.应用场景
斐波那契查找算法通常用于有序数列的查找操作，特别是针对大型有序数列的查找。这种算法常常被用于数据库索引、电话簿、目录和其他类似的应用程序中，因为它具有较好的时间复杂度和空间复杂度。具体应用场景如下：
- 在大型数据集中进行查找时，斐波那契查找算法比二分查找算法更快。
- 斐波那契查找算法可用于从有序数列中查找给定值的位置，这些数列可以是数组、链表、二叉搜索树或其他数据结构。
- 斐波那契查找算法可以优化对数据库索引的查找操作，这可以提高数据库查询的性能。
- 斐波那契查找算法还可以用于图形搜索，例如在网格或树形结构中查找最短路径。
斐波那契查找算法适用于需要在大型有序数据集中查找给定值的情况，特别是在需要高效查询、在数据量巨大时使用，因为它可以减少比较操作的数量，从而提高查找效率。
🔎4.示例
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) 。
腾讯云开发者
