查找算法之斐波那契查找

由来：

斐波那契数列：前两项之和等于第三项，假如下标为k，那么f[k] = f[k-1] + f[k-2]。如果将一条长为f[k]的线段分为两条线段，它们的长度分别为f[k-1]和f[k-2],这种分法很接近黄金分割比。斐波那契查找由此而来。

 简介：

如果一个数组的长度是f[k]，那么就可以把它分为两个子数组，一个的长度是f[k-1]，另一个的长度是f[k-2]。例：k = 5，f[k] = 8，f[k-1] = 5，f[k-2] = 3

 如果这样分割，那么中轴的下标pivot = left + f[k-1] - 1 =  0 + 5 - 1 = 4

 斐波那契查找原理与二分查找相同，只是不是折半划分子数组，而是按照黄金分割的比例进行划分。例子如下：

 代码：

    /**
     * 斐波那契查找
     * @param arr               从小到大的有序数组
     * @param fibonacciLength   斐波那契数组的长度，保证f[fibonacciLength - 1] > arr.length
     * @param value             目标值
     * @return
     */
    public static List<Integer> fibonacciSearch(int[] arr, int fibonacciLength, int value) {
        if (arr == null || arr.length == 0) {
            return Collections.emptyList();
        }
        //得到一个斐波那契数组，长度为k
        int[] fibonacciArray = createFibonacciArray(fibonacciLength);
        //得到k的值，使得fibonacciArray[k] >= arr.length
        int k = 0;
        while (arr.length > fibonacciArray[k]) {
            k++;
        }
        //如果arr.length < fibonacciArray[k]，那么就将数组的长度扩充到fibonacciArray[k]，用数组最大的值进行填充
        int[] newArr = Arrays.copyOf(arr, fibonacciArray[k]);
        for (int i = arr.length; i < newArr.length; i++) {
            newArr[i] = arr[arr.length - 1];
        }
        //中轴下标
        int pivot;
        //左索引
        int left = 0;
        //右索引
        int right = arr.length - 1;
        //与目标值相同的下标集合
        List<Integer> result = new ArrayList<>(arr.length);
        //利用二分查找的原理去查找目标值
        while (left <= right) {
            pivot = left + fibonacciArray[k-1] - 1;
            if (value < newArr[pivot]) {
                //往左边找
                right = pivot - 1;
                k -= 1;
            } else if (value > newArr[pivot]) {
                //往右边找
                left = pivot + 1;
                k -= 2;
            } else {
                //目标值等于中轴值，如果中轴下标指向的是扩充的值，那么pivot = arr.length - 1
                if (pivot > arr.length - 1) {
                    pivot = arr.length - 1;
                }
                //向左向右看看紧挨着的值有没有等于arr[pivot]，如果有，将它们的下标也返回
                int temp = pivot;
                while (temp >= 0 && arr[temp] == arr[pivot]) {
                    //向左查找
                    result.add(temp);
                    temp--;
                }
                temp = pivot + 1;
                while (temp <= arr.length - 1 && arr[temp] == arr[pivot]) {
                    //向右查找
                    result.add(temp);
                    temp++;
                }
                return result;
            }

        }
        //没有找到
        return Collections.emptyList();
    }

    /**
     * 生成斐波那契数组
     * @param fibonacciLength  数组的长度
     * @return
     */
    private static int[] createFibonacciArray(int fibonacciLength) {
        int[] fibonacciArray = new int[fibonacciLength];
        fibonacciArray[0] = 1;
        fibonacciArray[1] = 1;
        for (int i = 2; i < fibonacciArray.length; i++) {
            fibonacciArray[i] = fibonacciArray[i - 1] + fibonacciArray[i - 2];
        }
        return fibonacciArray;
    }