查找算法之斐波那契查找算法

斐波那契（黄金分割法）查找算法

（一）算法简介

（1）斐波那契数列

在讲算法之前，我们先介绍一下斐波那契数列，该数列公式为F(K) = F(k-1) + F(k-2)，即 1、1、2、3、5、8、13、21……。我们还知道，F(k-1)/f(K)随着K的递增，该数越来越接近黄金分割比例，所以该方法也叫黄金分割法。

（2）查找算法

对于一个数组来说，如果数组长度为斐波那契数列中的某一个数字，那么我们就可以用黄金分割比例来分割该数组。当然，如果数组长度没有达到要求，那么我们可以尝试它扩大来满足要求，所以这就是算法的要求。

其实，该算法的本质也还是二分法，只不过跟插入排序法一样，也是将目标的mid值改变成其它的，以至于分割的结果不一样，查找的效果也不一样。

那么具体是怎样分割的呢？

这里用图片直观理解一下：

也就是说，真正需要我们做的是找到这个mid，这里给出公式：mid = F(k-1)-1，你也可以从图片中看出来，数组下表是从：0~F[k]-1，将原来的分成两半，再比较来查找。

（二）代码解释

（1）main 主方法，不多解释

public static void main(String[] args) {
    int[] arr = { 1, 2, 3, 4, 5, 99, 100 };
    System.out.println("index = " + FibSearch(arr, 99));
}
1
2
3
4

（2）获取一个斐波那契数组，简单不多解释

public static int maxSize = 20;

public static int[] getFibonacci() {
    int[] fib = new int[maxSize];
    fib[0] = 1;
    fib[1] = 1;
    for (int i = 2; i < maxSize; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib;
}
1
2
3
4
5
6
7
8
9
10
11

(3)斐波那契查找算法

public static int FibSearch(int[] arr, int value) {
    int low = 0;
    int high = arr.length - 1;
    int mid = 0;
    int[] fib = getFibonacci();
    int k = 0;
    while (high >= fib[k] - 1) {
        k++;
    }

    int[] tmp = Arrays.copyOf(arr, fib[k]);
    for (int i = arr.length; i < fib[k]; ++i) {
        tmp[i] = arr[high];
    }

    while (low <= high) {
        mid = low + fib[k - 1] - 1;
        if (value < tmp[mid]) {
            high = mid - 1;
            k--;
        } else if (value > tmp[mid]) {
            low = mid + 1;
            k -= 2;
        } else {
            if (mid <= high) {
                return mid;
            } else {
                return high;
            }
        }
    }
    return -1;
}
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

• 在15行之前都是对数组的一个拷贝、扩容处理，以到达黄金分割的目的
• 后面mid = low + fib[k - 1] - 1就可以成功定位mid的位置，最后比较，查找
• 注意一点：最后如果找到还要判断一下，如果返回的是在原数组之内的下标，可以直接返回，如果返回的是数组之外的下标，得返回原数组最后那个，即 high

位置，最后比较，查找

• 注意一点：最后如果找到还要判断一下，如果返回的是在原数组之内的下标，可以直接返回，如果返回的是数组之外的下标，得返回原数组最后那个，即 high