斐波那契查找算法

算法原理：

斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。

1. 构建一个斐波那契数列
2. 扩展被查询数列：在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为F[n](如果要补充元素，则补充重复最后一个元素，直到满足F[n]个元素)
3. 查找元素：对扩展后的被查询数列进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。

时间复杂度：

时间复杂度 O(log 2 n )

对比二分法查找：

二者时间复杂度一样都是O(log 2 n )，但是与二分法查找相比，

斐波那契查找的优点是它只涉及加法和减法运算，而不用除法，而除法比加减法要占用更多的时间，

因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定。

package com.study.java.al;

import java.util.Arrays;

/**
 *
 * 斐波那契查找算法
 * 步骤概述：
 * 1. 构建一个斐波那契数列
 * 2. 扩展被查询数列：在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为F[n](如果要补充元素，则补充重复最后一个元素，直到满足F[n]个元素)，
 * 3. 查找元素：对扩展后的被查询数列进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
 */

/**
 * @author ahdkkyxq
 */
public class FibonacciSearch {

    /**
     * @param args
     */
    public final static int MAXSIZE = 10;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] f = fibonacci();
        // 打印fib数组
        System.out.println("斐波那契数列: "+Arrays.toString(f));
        int[] data = {1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88};
        System.out.println("被查询数列: "+Arrays.toString(data));
        int search = 39;
        System.out.println("查询目标: "+search);
        int position = fibonacciSearch(data, search);
        System.out.println("值" + search + "的元素位置为：" + position);
    }

    /**
     * 斐波那契数列
     *
     * @return
     */
    public static int[] fibonacci() {
        int[] f = new int[MAXSIZE];
        int i = 0;
        f[0] = 1;
        f[1] = 1;
        for (i = 2; i < MAXSIZE; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    public static int fibonacciSearch(int[] data, int key) {
        int low = 0;
        int high = data.length - 1;
        int mid = 0;

        // 斐波那契分割数值下标
        int k = 0;

        // 序列元素个数
        int i = 0;

        // 获取斐波那契数列
        int[] f = fibonacci();

        // 获取斐波那契分割数值下标
        while (data.length > f[k] - 1) {
            k++;
        }

        // 创建临时数组,长度为fib的值-1，并复制原数组的内容到新数组
        int[] temp = new int[f[k] - 1];
        for (int j = 0; j < data.length;j++){
            temp[j] = data[j];
        }
        // 序列补充至f[k]个元素
        // 补充的元素值为最后一个元素的值
        for (i = data.length; i < f[k] - 1; i++) {
            temp[i] = temp[high];
        }
        // 打印数组
        System.out.println("被查询数组扩容: "+Arrays.toString(temp));

        while (low <= high) {
            // low：起始位置
            // 前半部分有f[k-1]个元素，由于下标从0开始
            // 则-1 获取 黄金分割位置元素的下标
            mid = low + f[k - 1] - 1;

            if (temp[mid] > key) {
                // 查找前半部分，高位指针移动
                high = mid - 1;
                // （全部元素） = （前半部分）+（后半部分）
                // f[k] = f[k-1] + f[k-1]
                // 因为前半部分有f[k-1]个元素，所以 k = k-1
                k = k - 1;
            } else if (temp[mid] < key) {
                // 查找后半部分，高位指针移动
                low = mid + 1;
                // （全部元素） = （前半部分）+（后半部分）
                // f[k] = f[k-1] + f[k-1]
                // 因为后半部分有f[k-1]个元素，所以 k = k-2
                k = k - 2;
            } else {
                // 如果为真则找到相应的位置
                if (mid <= high) {
                    return mid;
                } else {
                    // 出现这种情况是查找到补充的元素
                    // 而补充的元素与high位置的元素一样
                    return high;
                }
            }
        }
        return -1;
    }
}

运算结果：

AAAA-07.png