Java斐波那契查找知识点（含面试大厂题和源码）

斐波那契查找（Fibonacci Search）是一种基于斐波那契数列的搜索算法，它在有序数组中查找特定元素。斐波那契查找是二分查找的一种优化版本，它使用斐波那契数列的特性来决定搜索区间的划分，从而减少比较次数。

斐波那契查找的工作原理：

1. 斐波那契数列：斐波那契查找使用斐波那契数列的特性，即 F(k) = F(k-1) + F(k-2)，其中 F(1) = 1 和 F(2) = 1。

2. 确定搜索范围：使用斐波那契数列中的数字来确定搜索区间的大小，使得搜索区间的长度尽可能接近斐波那契数。

3. 区间划分：选择斐波那契数列中的两个连续数字 F[k-2] 和 F[k-1]，其中 F[k-2] 接近于数组的当前搜索范围。将数组的搜索范围划分为三个部分：[0, F[k-2]-2]，[F[k-2]-1, F[k-1]-2]，和 [F[k-1]-1, high]。

4. 查找元素：在这三个区间内进行查找，根据元素的值与中间值的比较结果，逐步缩小搜索范围。

5. 递归或迭代：使用递归或迭代的方式继续在缩小后的范围内进行搜索，直到找到元素或搜索范围无效。

斐波那契查找的Java实现：

public class FibonacciSearch {
    private static int[] fib = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597};

    public int fibonacciSearch(int[] arr, int x) {
        int n = arr.length;
        int k = 0;
        // Find the index `k` such that fib[k] is just greater than or equal to n
        while (fib[k] < n) {
            k++;
        }

        // Marks the eliminated range from front
        int offset = -1;

        // fib[k-2] is the smallest Fibonacci number greater than or equal to n
        int fibKMinus2 = fib[k - 2];
        int fibKMinus1 = fib[k - 1];

        while (n > 1) {
            // Prevents (n - fibKMinus2) underflow
            int i = Math.min(offset + fibKMinus2, n - 1);

            // Compare `x` with the element at index `i`
            if (arr[i] < x) {
                n = fibKMinus2;
                fibKMinus1 = fibKMinus2;
                fibKMinus2 = fib[k - 3];
                offset = i;
            } else if (arr[i] > x) {
                fibKMinus1 = fib[k - 2];
                fibKMinus2 = fib[k - 3];
                k = 3;
            } else {
                return i;
            }
        }

        // Comparing the last element with `x`
        if (n == 1 && arr[offset + 1] == x) {
            return offset + 1;
        }

        // Element not found
        return -1;
    }

    public static void main(String[] args) {
        FibonacciSearch search = new FibonacciSearch();
        int[] arr = {10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100};
        int x = 85;
        int result = search.fibonacciSearch(arr, x);
        if (result >= 0) {
            System.out.println("Element found at index " + result);
        } else {
            System.out.println("Element not found.");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

在面试中，斐波那契查找可以作为一个展示你对搜索算法深度理解的话题。通过实现斐波那契查找，可以展示你对算法性能优化的理解和应用能力。希望这些知识点和示例代码能够帮助你更好地准备面试！斐波那契查找是一种在有序数组中查找元素的算法，它利用斐波那契数列的特性来减少搜索次数。以下是三道可能出现在大厂面试中的与斐波那契查找相关的编程题目，以及相应的Java源码实现。

题目 1：斐波那契查找实现

描述：
实现斐波那契查找算法，用于在有序数组中查找特定元素。

示例：

输入: arr = [1, 3, 7, 10, 15, 20], x = 7
输出: 2
1
2

Java 源码：

public class FibonacciSearch {
    private static final int[] fib = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};

    public int fibonacciSearch(int[] arr, int x) {
        int n = arr.length;
        int fibMMm2 = 0;
        int fibMMm1 = 1;
        int fibM = fibMMm2 + fibMMm1;

        // 获取大于或等于 n 的最小斐波那契数
        while (fibM < n) {
            fibMMm2 = fibMMm1;
            fibMMm1 = fibM;
            fibM = fibMMm2 + fibMMm1;
        }

        // 标记斐波那契数列中的两个连续数字
        int offset = -1;

        // 初始化 fibonacci 索引的前两个元素
        int i = fibMMm2;

        // 斐波那契查找
        while (i < n) {
            if (arr[i] < x) {
                // 减小搜索范围的上限
                offset = i;
                fibM = fibMMm1;
                fibMMm1 = fibMMm2;
                fibMMm2 = fibM - fibMMm1;
                i = offset + fibMMm1;
            } else if (arr[i] > x) {
                // 减小搜索范围的下限
                fibM = fibMMm1;
                fibMMm1 = fibMMm2;
                fibMMm2 = fibM - fibMMm1;
                i = fibMMm2 + offset + 1;
            } else {
                // 找到元素，返回索引
                return i;
            }
        }

        // 元素不在数组中，返回-1
        return -1;
    }

    public static void main(String[] args) {
        FibonacciSearch solution = new FibonacciSearch();
        int[] arr = {1, 3, 7, 10, 15, 20};
        int x = 7;
        int result = solution.fibonacciSearch(arr, x);
        System.out.println("Index of " + x + ": " + result);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

题目 2：斐波那契查找优化

描述：
在斐波那契查找中，如果数组中的元素数量不是斐波那契数，算法的性能会有所下降。请实现一种优化，使得算法在任何数组大小下都能达到最佳性能。

示例：

输入: arr = [2, 3, 4, 5, 6, 7, 8, 10], x = 5
输出: 4
1
2

Java 源码：

// 优化版本的斐波那契查找与题目 1 类似，需要在查找前对数组大小进行调整或使用其他方法来优化性能。
1

题目 3：斐波那契查找与二分查找的比较

描述：
给定一个足够大的有序数组，比较斐波那契查找和二分查找在该数组上的性能。实现两种查找算法，并给出你的分析。

示例：

// 性能比较通常需要实际运行算法并测量运行时间，因此这里不提供具体的输出示例。
1

Java 源码：

// 实现二分查找和斐波那契查找，并在给定数组上运行这两种算法，比较它们的性能。
1

这些题目和源码展示了斐波那契查找在解决实际问题中的应用。在面试中，能够根据问题的特点选择合适的算法并实现其解决方案是非常重要的。希望这些示例能够帮助你更好地准备面试！