查找算法(4)--Fibonacci search--斐波那契查找

1.斐波那契查找

(1)说明

　　在介绍斐波那契查找算法之前，我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。

　　黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。

　　0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。

　　大家记不记得斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。

　　(2)基本思想

也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

相对于折半查找，一般将待比较的key值与第mid=（low+high）/2位置的元素比较，比较结果分三种情况：

　　[1]相等，mid位置的元素即为所求

　　[2]>，low=mid+1;

[3]<，high=mid-1。

斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;

开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种

　　[1]相等，mid位置的元素即为所求

　　[2]>，low=mid+1,k-=2;

　　说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。

　　[3]<，high=mid-1,k-=1。

　　说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归的应用斐波那契查找。

(3)复杂度分析

　　最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。

2.代码

public final static int MAXSIZE = 20;

/**

 * 斐波那契数列

 *

 * @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++;

    }

    //创建临时数组

    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];

    }

    //打印

    for (int j : temp) {

        System.out.print(j + " ");

    }

    System.out.println();

    //开始查找

    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;

}

public static void main(String[] args) {

    int[] f = fibonacci();

    for (int i : f) {

        System.out.print(i + " ");

    }

    System.out.println();

    int[] data = {1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88};

    int search = 39;

    int position = fibonacciSearch(data, search);

    System.out.println("值" + search + "的元素位置为：" + position);

}

巴特西