java中斐波那契查找方法怎么使用

Java中斐波那契查找方法怎么使用

斐波那契查找（Fibonacci Search）是一種基于斐波那契數列的搜索算法，適用于在有序數組中進行查找操作。與二分查找類似，斐波那契查找也是一種分治算法，但它通過斐波那契數列來確定分割點，從而在某些情況下能夠減少比較次數。本文將詳細介紹如何在Java中使用斐波那契查找方法。

1. 斐波那契查找的基本原理

斐波那契查找的核心思想是利用斐波那契數列來確定查找范圍的分割點。斐波那契數列是一個無限數列，其定義如下：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n >= 2)

斐波那契數列的前幾項為：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

在斐波那契查找中，我們首先找到一個斐波那契數 F(k)，使得 F(k) 大于或等于數組的長度 n。然后，我們將數組的長度擴展到 F(k)，并使用斐波那契數列來確定分割點。

2. 斐波那契查找的步驟

斐波那契查找的步驟如下：

1. 初始化：找到最小的斐波那契數 F(k)，使得 F(k) 大于或等于數組的長度 n。
2. 擴展數組：將數組的長度擴展到 F(k)，并用數組的最后一個元素填充擴展的部分。
3. 查找：使用斐波那契數列來確定分割點，逐步縮小查找范圍，直到找到目標元素或確定目標元素不存在。

3. Java實現斐波那契查找

下面是一個在Java中實現斐波那契查找的示例代碼：

public class FibonacciSearch {

    // 生成斐波那契數列
    private static int[] generateFibonacci(int n) {
        int[] fib = new int[n];
        fib[0] = 0;
        fib[1] = 1;
        for (int i = 2; i < n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib;
    }

    // 斐波那契查找
    public static int fibonacciSearch(int[] arr, int key) {
        int n = arr.length;
        int[] fib = generateFibonacci(20); // 生成足夠大的斐波那契數列

        // 找到最小的斐波那契數 F(k) >= n
        int k = 0;
        while (fib[k] < n) {
            k++;
        }

        // 擴展數組
        int[] temp = new int[fib[k]];
        System.arraycopy(arr, 0, temp, 0, n);
        for (int i = n; i < fib[k]; i++) {
            temp[i] = arr[n - 1];
        }

        // 開始查找
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + fib[k - 1] - 1;
            if (key < temp[mid]) {
                high = mid - 1;
                k -= 1;
            } else if (key > temp[mid]) {
                low = mid + 1;
                k -= 2;
            } else {
                if (mid < n) {
                    return mid;
                } else {
                    return n - 1;
                }
            }
        }

        return -1; // 未找到
    }

    public static void main(String[] args) {
        int[] arr = {10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100};
        int key = 85;
        int index = fibonacciSearch(arr, key);
        if (index != -1) {
            System.out.println("元素 " + key + " 在數組中的索引為: " + index);
        } else {
            System.out.println("元素 " + key + " 不在數組中");
        }
    }
}

4. 代碼解析

• generateFibonacci 方法用于生成斐波那契數列。我們生成了一個足夠大的斐波那契數列，以確保能夠覆蓋數組的長度。
• fibonacciSearch 方法實現了斐波那契查找算法。首先找到最小的斐波那契數 F(k) 大于或等于數組的長度 n，然后擴展數組并使用斐波那契數列來確定分割點。
• main 方法中，我們定義了一個有序數組和一個目標元素，調用 fibonacciSearch 方法進行查找，并輸出結果。

5. 總結

斐波那契查找是一種高效的查找算法，適用于有序數組。它通過斐波那契數列來確定分割點，從而在某些情況下能夠減少比較次數。本文介紹了斐波那契查找的基本原理、步驟，并提供了一個Java實現的示例代碼。希望本文能夠幫助你理解并掌握斐波那契查找的使用方法。