详解Java Fibonacci Search斐波那契搜索算法代码实现

什么是斐波那契搜索算法？

斐波那契搜索算法是一种基于斐波那契数列的搜索算法，它主要用于在一个有序的列表中查找指定的元素。斐波那契搜索算法相对于传统的二分查找算法，在查找长度较大的有序列表时，具有更好的效率表现。

算法实现

以下是按照Java语言实现的完整的斐波那契搜索算法代码：

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

    while (fibM < n) {
        fibMMm2 = fibMMm1;
        fibMMm1 = fibM;
        fibM = fibMMm2 + fibMMm1; 
    }
    int offset = -1; 
    while (fibM > 1) {
        int i = Math.min(offset+fibMMm2, n-1);
        if (nums[i] < target) {
            fibM = fibMMm1;
            fibMMm1 = fibMMm2;
            fibMMm2 = fibM - fibMMm1;
            offset = i;
        } else if (nums[i] > target) {
            fibM = fibMMm2;
            fibMMm1 = fibMMm1 - fibMMm2;
            fibMMm2 = fibM - fibMMm1;
        } else {
            return i;
        }
    }
    if (fibMMm1 == 1 && nums[offset+1] == target)
        return offset+1;

    return -1; 
}

算法解释

• （1）计算n位于斐波那契数列的位置，使得F(k)-1恰好大于等于n（由于数组下标从0开始，因此使用n-1）。

• （2）将原数组扩展至F(k)-1的长度，不足部分用原数组中最后一个元素填充。

• （3）从F(k)-1位置开始比较，如果该位置元素等于要查找的元素，则返回。如果小于要查找的元素，则将范围缩小至右侧的F(k-1)个元素，否则将范围缩小至左侧的F(k-2)个元素。重复以上步骤直至找到要查找的元素或搜索范围已经缩小为0。

示例

对于下面一组数，我们可以使用斐波那契搜索算法进行查找：

int[] nums = {1, 3, 5, 7, 9, 11, 13, 15};
int target1 = 3;
int target2 = 6;
System.out.println(fibonacciSearch(nums, target1)); // 输出：1，表示查找到了元素3，下标为1
System.out.println(fibonacciSearch(nums, target2)); // 输出：-1，表示没有查找到元素6

结果表明，对于给定的数组，斐波那契搜索算法可以高效地查找指定的元素，而对于不存在的元素，算法会返回-1。