【算法系列 | 12】深入解析查找算法之—斐波那契查找

序言

心若有阳光，你便会看见这个世界有那么多美好值得期待和向往。

决定开一个算法专栏，希望能帮助大家很好的了解算法。主要深入解析每个算法，从概念到示例。

我们一起努力，成为更好的自己！

今天第12讲，讲一下查找算法的—斐波那契查找

一、算法介绍

斐波那契查找算法是一种基于黄金分割的有序查找算法，通过斐波那契数列的特性，在有序序列中快速定位目标元素的位置。

1.1 原理介绍

它结合了二分查找和黄金分割的思想。这个算法的基本原理如下：

1. 序列构建： 首先，需要一个有序的数组或序列。这个数组的长度通常是斐波那契数列中的一个值，这有助于在查找过程中对数组进行分割。

2. 斐波那契数列： 斐波那契数列是一组按以下递归关系定义的数字序列：F(0) = 0，F(1) = 1，F(n) = F(n-1) + F(n-2)（n > 1）。通常，斐波那契数列的前几项是：0, 1, 1, 2, 3, 5, 8, 13, 21, ...

3. 查找过程： 对于一个有序序列，首先选择一个斐波那契数列中的值，使得这个值大于或等于待查找序列的长度，然后使用这个斐波那契数列的值将序列分成两个部分。这两个部分的长度之比就是相邻两个斐波那契数的比例。

4. 比较： 比较要查找的元素与序列中分割点的元素。如果相等，则找到了目标元素；如果待查找元素小于分割点元素，继续在前半部分进行查找；如果待查找元素大于分割点元素，继续在后半部分进行查找。

5. 迭代： 重复上述步骤，不断缩小查找范围，直到找到目标元素或确定元素不在序列中。

示例说明

假设有一个有序数组 arr，长度为 n，而 n 正好是斐波那契数列中的某个值。为了简化，我们可以选择 n 为斐波那契数列中的某个值，比如 F(5) = 5，所以 n = 5。那么，我们有一个有序数组 arr，长度为 5。

arr = [1, 3, 5, 7, 9]

接下来，我们要查找值为 5 的元素在数组中的位置。以下是斐波那契查找的步骤：

1.?选择斐波那契数列的值： 在斐波那契数列中找到一个最小的值，使得 F(k) >= n，其中 k 是最小可能满足的索引。在这个例子中，我们选择 F(5) = 5。

?2.?分割数组： 将数组分成两个部分，长度比例为斐波那契数列中的两个相邻值的比例。在这个例子中，我们有两部分，长度比例是 3:2。

? ? ?arr_left = [1, 3, 5]?arr_right = [7, 9]

3.? 比较与查找： 比较要查找的元素（5）与分割点元素（arr[2] = 5）。如果相等，找到了目标元素。如果待查找元素小于分割点元素，继续在前半部分进行查找。如果待查找元素大于分割点元素，继续在后半部分进行查找。

?在这个例子中，5 等于分割点元素，所以我们找到了目标元素的位置。

4. 迭代： 重复上述步骤，直到找到目标元素或确定元素不在序列中。

1.2 优缺点

优点：

1. 适用性广泛： 斐波那契查找适用于有序序列，尤其在序列长度接近斐波那契数列的某个值时效果更佳。相较于二分查找，斐波那契查找能够在某些特定情况下减少查找次数。

2. 更好的平衡： 由于斐波那契查找使用黄金分割比例进行分割，使得分割后的两个子序列的长度比例更加接近，有助于保持查找的平衡性。

3. 相对均匀的分割： 斐波那契查找相对于其他分割方法，如二分查找，能够产生更为均匀的分割，有助于在查找过程中更快地接近目标元素。

缺点：

1. 数组长度限制： 斐波那契查找要求待查找的序列长度必须是斐波那契数列中的某个值，这在实际应用中可能不太灵活，特别是当数据规模不是恰好是斐波那契数列中的某个值时，可能需要对数据进行补齐。

2. 比较次数不稳定： 斐波那契查找在某些情况下可能会比二分查找效果更好，但并不是在所有情况下都表现更好。具体的性能取决于待查找数据的分布情况和序列的长度。在一些场景下，二分查找可能更为稳定。

3. 计算斐波那契数列： 为了选择合适的斐波那契数列的值，需要事先计算斐波那契数列，这可能涉及到一些计算成本，特别是对于较大的数据集。

总体来说，斐波那契查找算法在某些特定条件下表现优秀，但在实际应用中需要谨慎选择，并根据具体情况考虑使用。在一些情况下，简单的二分查找可能更加实用和高效。

1.3 复杂度

时间复杂度：

1. 查找过程： 斐波那契查找的主要操作是不断地缩小查找范围，通过比较待查找元素与分割点元素来确定继续在前半部分还是后半部分进行查找。在每一步操作中，都可以将待查找范围缩小为原来的黄金分割比例，即约为 0.618。

2. 时间复杂度： 斐波那契查找的时间复杂度可以表示为 O(log n)，其中 n 是待查找序列的长度。与二分查找相比，它的复杂度相对更低。

空间复杂度：

1. 常数空间： 斐波那契查找算法的空间复杂度非常低。它只需要常数级别的额外空间来存储一些中间变量，如斐波那契数列的值、分割点等。

2. O(1)： 因此，斐波那契查找的空间复杂度可以表示为 O(1)。

总体来说，斐波那契查找在时间复杂度和空间复杂度上都相对较低，这使得它在某些特定场景下成为一个有效的查找算法。

但需要注意，实际效果还受到数据分布等因素的影响，因此在选择查找算法时，需要综合考虑具体情况。

1.4 使用场景

斐波那契查找算法在一些特定的场景下表现良好，适用于如下情况：

1. 有序序列： 斐波那契查找要求待查找的序列是有序的，因为它是基于比较来缩小查找范围的。如果序列无序，需要先进行排序操作。

2. 长度接近斐波那契数： 算法对序列的长度有一定的要求，最好是恰好是斐波那契数列中的某个值。在实际应用中，可以选择最接近并大于待查找序列长度的斐波那契数。

3. 分布均匀： 如果数据在序列中的分布相对均匀，斐波那契查找可以更好地发挥其优势。这是因为它能够在分割序列时保持更好的平衡。

4. 查找频繁但数据变动不频繁： 如果对同一序列进行多次查找而且序列基本保持不变，斐波那契查找的一些前期计算可以提前完成，然后多次使用相同的计算结果进行查找，从而提高效率。

5. 适用于内存有限的情况： 斐波那契查找只需要常数级别的额外空间，因此在内存有限的情况下比一些其他算法更为适用。

需要注意的是，斐波那契查找并不总是比其他查找算法更好，它在特定的条件下才会表现出色。在实际应用中，需要根据具体情况选择最适合的查找算法。

二、代码实现

2.1 Java代码实现

2.1.1 代码示例

public class FibonacciSearch {

    // 辅助函数：生成斐波那契数列
    private static int[] generateFibonacci(int n) {
        int[] fibonacci = new int[n];
        fibonacci[0] = 0;
        fibonacci[1] = 1;

        for (int i = 2; i < n; i++) {
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        }

        return fibonacci;
    }

    // 斐波那契查找算法
    public static int fibonacciSearch(int[] arr, int key) {
        int n = arr.length;
        
        // 生成斐波那契数列，找到最接近且大于等于 n 的值
        int[] fibonacci = generateFibonacci(n);
        int k = 0;
        while (fibonacci[k] < n) {
            k++;
        }

        // 将数组扩展到斐波那契数列的长度
        int[] temp = new int[fibonacci[k]];
        System.arraycopy(arr, 0, temp, 0, n);

        int low = 0;
        int high = n - 1;

        // 主要查找过程
        while (low <= high) {
            int mid = low + fibonacci[k - 1] - 1;

            if (key < temp[mid]) {
                high = mid - 1;
                k -= 1;
            } else if (key > temp[mid]) {
                low = mid + 1;
                k -= 2;
            } else {
                // 找到了目标元素，需要判断返回的是原数组中的索引还是扩展数组中的索引
                return Math.min(mid, high);
            }
        }

        // 未找到目标元素
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
        int key = 7;

        int result = fibonacciSearch(arr, key);

        if (result != -1) {
            System.out.println("元素 " + key + " 在数组中的索引为：" + result);
        } else {
            System.out.println("元素 " + key + " 不在数组中");
        }
    }
}

2.1.2 代码详解

1. generateFibonacci方法：生成斐波那契数列，参数 n 表示生成数列的长度。

2. fibonacciSearch方法：实现了斐波那契查找算法。首先，通过调用 generateFibonacci 方法生成斐波那契数列，然后找到最接近并大于等于数组长度的斐波那契数。接着，将原数组扩展到斐波那契数列的长度，再进行主要的查找过程。查找过程中，根据比较的结果不断缩小查找范围，直到找到目标元素或确定元素不在序列中。

3. main方法：在这里，创建一个有序数组 arr，并调用 fibonacciSearch 方法查找元素 7 的索引。最后，输出查找结果。

2.1.3 运行结果

元素 7 在数组中的索引为：3

2.2 Python代码实现

2.2.1 代码示例

def generate_fibonacci(n):
    """生成斐波那契数列"""
    fibonacci = [0, 1]
    while fibonacci[-1] < n:
        fibonacci.append(fibonacci[-1] + fibonacci[-2])
    return fibonacci


def fibonacci_search(arr, key):
    """斐波那契查找算法"""
    n = len(arr)

    # 生成斐波那契数列，找到最接近且大于等于 n 的值
    fibonacci = generate_fibonacci(n)
    k = 0
    while fibonacci[k] < n:
        k += 1

    # 将数组扩展到斐波那契数列的长度
    temp = arr + [arr[-1]] * (fibonacci[k] - n)

    low, high = 0, n - 1

    # 主要查找过程
    while low <= high:
        mid = low + fibonacci[k - 1] - 1

        if key < temp[mid]:
            high = mid - 1
            k -= 1
        elif key > temp[mid]:
            low = mid + 1
            k -= 2
        else:
            # 找到了目标元素，返回原数组中的索引
            return min(mid, n - 1)

    # 未找到目标元素
    return -1

if __name__ == '__main__':

    # 测试
    arr = [1, 3, 5, 7, 9, 11, 13, 15]
    key = 7
    
    result = fibonacci_search(arr, key)

    if result != -1:
        print(f"元素 {key} 在数组中的索引为：{result}")
    else:
        print(f"元素 {key} 不在数组中")

2.2.2 代码详解

1. generate_fibonacci 函数：用于生成斐波那契数列，直到数列的最后一个值大于等于给定的参数 n。

2. fibonacci_search 函数：实现了斐波那契查找算法。首先，调用 generate_fibonacci 函数生成斐波那契数列，然后找到最接近并大于等于数组长度的斐波那契数。接着，将原数组扩展到斐波那契数列的长度，再进行主要的查找过程。查找过程中，根据比较的结果不断缩小查找范围，直到找到目标元素或确定元素不在序列中。

在测试部分，创建一个有序数组 arr，并调用 fibonacci_search 函数查找元素 7 的索引。最后，输出查找结果。

2.2.3 运行结果

元素 7 在数组中的索引为：3

好啦，今天就到这里啦，下期见喽~~🙉

三、图书推荐

3.1 图书名称

图书名称：《Pandas数据分析》

Pandas是强大且流行的库，是Python中数据科学的代名词。这本书会介绍如何使用Pandas对真实世界的数据集进行数据分析，如股市数据、模拟黑客攻击的数据、天气趋势、地震数据、葡萄酒数据和天文数据等。

Pandas使我们能够有效地处理表格数据，从而使数据整理和可视化变得更容易。等不及的小伙伴，可以点击这个链接先睹为快?《Pandas数据分析》

3.2 图书介绍?

3.3 参与方式

图书数量：本次送出 2?本 ? ！！！??????
活动时间：截止到 2024-01-09?12:00:00

抽奖方式：

• 评论区随机抽取小伙伴！

留言内容，以下方式都可以：

• 根据文章内容进行高质量评论

参与方式：关注博主、点赞、收藏，评论区留言?

3.4 中奖名单

🍓🍓 获奖名单🍓🍓

?中奖名单：请关注博主动态

名单公布时间：2024-01-09?下午