费氏搜寻法 收敛速度更快

说明
二分搜寻法每次搜寻时，都会将搜寻区间分为一半，所以其搜寻时间为O(log(2)n)，log(2)表示
以2为底的log值，这边要介绍的费氏搜寻，其利用费氏数列作为间隔来搜寻下一个数，所以区
间收敛的速度更快，搜寻时间为O(logn)。
解法
费氏搜寻使用费氏数列来决定下一个数的搜寻位置，所以必须先制作费氏数列，这在之前有提
过；费氏搜寻会先透过公式计算求出第一个要搜寻数的位置，以及其代表的费氏数，以搜寻对
象10个数字来说，第一个费氏数经计算后一定是F5，而第一个要搜寻的位置有两个可能，例如
若在下面的数列搜寻的话（为了计算方便， 通常会将索引0订作无限小的数，而数列由索引1
开始）：
-infin; 1 3 5 7 9 13 15 17 19 20
如果要搜寻5的话，则由索引F5 = 5开始搜寻，接下来如果数列中的数小于指定搜寻值时，就往
左找，大于时就向右，每次找的间隔是F4、F3、F2来寻找，当费氏数为0时还没找到，就表示
寻找失败，如下所示：

由于第一个搜寻值索引F5 = 5处的值小于19，所以此时必须对齐数列右方，也就是将第一个搜
寻值的索引改为F5+2 = 7，然后如同上述的方式进行搜寻，如下所示：


至于第一个搜寻值是如何找到的？我们可以由以下这个公式来求得，其中n为搜寻对象的个数：


如果数列number在索引5处的值小于指定的搜寻值，则第一个搜寻位置就是索引5的位置，如果
大于指定的搜寻值，则第一个搜寻位置必须加上m，也就是F5 + m = 5 + 2 = 7，也就是索引7的
位置，其实加上m的原因，是为了要让下一个搜寻值刚好是数列的最后一个位置。
费氏搜寻看来难懂，但只要掌握Fx + m = n这个公式，自己找几个实例算一次，很容易就可以理
解；费氏搜寻除了收敛快速之外，由于其本身只会使用到加法与减法，在运算上也可以加快。

/**
 * @author:         吴永行
 * @dateTime:      2014-3-24 下午10:13:33
 * @description:
 *
 */
package 经典算法大全;

import java.util.Random;
import java.util.Scanner;

public class _45_费氏搜寻法 {

    /**
     * @author:         吴永行
     * @dateTime:      2014-3-24 下午9:25:31
     * @description:
     * @param args
     *
     */

    static final int MAX = 10;

    static final void swap(int[] a, int i, int j) {
        int t;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    static int Fib[] = new int[MAX];

    public static void main(String[] args) {

        int number[] = new int[MAX + 1];
        int i, find = 0;
        Random random = new Random();
        System.out.format("排序前：");
        for (i = 0; i < MAX; i++) {
            number[i] = Math.abs(random.nextInt()) % 100;
            System.out.format("%d ", number[i]);
        }
        quicksort(number, 1, MAX);
        System.out.format("数列：");
        for (i = 1; i <= MAX; i++)
            System.out.format("%d ", number[i]);
        System.out.format("\n输入搜寻值：");
        Scanner in = new Scanner(System.in);
        find = in.nextInt();
        if ((i = fibsearch(number, find)) >= 0)
            System.out.format("\n找到数值于索引%d ", i);
        else
            System.out.format("\n找不到数值");
        System.out.format("\n");

    }

    /**
     * @author:         吴永行
     * @dateTime:      2014-3-24 下午9:28:17
     * @description:
     * @param number
     * @param find
     * @return
     *
     */
    private static int fibsearch(int[] number, int find) {
        int i, x, m;
        createfib();
        for (int j : Fib) {
            System.out.print(j+ "\t");
        }
        x = findx(MAX + 1, find);
        m = MAX - Fib[x];
        System.out.format("\nx = %d, m = %d, Fib[x] = %d\n\n", x, m, Fib[x]);
        x--;
        i = x;
        if (number[i] < find)
            i += m;
        while (Fib[x] > 0) {
            if (number[i] < find)
                i += Fib[--x];
            else if (number[i] > find)
                i -= Fib[--x];
            else
                return i;
        }
        return -1;
    }

    /**
     * @author:         吴永行
     * @dateTime:      2014-3-24 下午10:16:46
     * @description:
     * @param i
     * @param find
     * @return
     *
     */
    private static int findx(int n, int find) {

        int i = 0;
        while (Fib[i] <= n)
            i++;
        i--;
        return i;
    }

    /**
     * @author:         吴永行
     * @dateTime:      2014-3-24 下午10:16:44
     * @description:
     *
     */
    private static void createfib() {
        int i;
        Fib[0] = 0;
        Fib[1] = 1;
        for (i = 2; i < MAX; i++)
            Fib[i] = Fib[i - 1] + Fib[i - 2];
    }

    /**
     * @author:         吴永行
     * @dateTime:      2014-3-23 下午9:41:21
     * @description:
     * @param number
     * @param i
     * @param j
     *
     */
    private static void quicksort(int[] number, int left, int right) {
        int q;
        if (left < right) {
            q = partition(number, left, right);
            quicksort(number, left, q - 1);
            quicksort(number, q + 1, right);
        }
    }

    /**
     * @author:         吴永行
     * @dateTime:      2014-3-23 下午9:42:02
     * @description:
     * @param number
     * @param left
     * @param right
     * @return
     *
     */
    private static int partition(int[] number, int left, int right) {
        int i, j, s;
        s = number[right];
        i = left - 1;
        for (j = left; j < right; j++) {
            if (number[j] <= s) {
                i++;
                swap(number, i, j);
            }
        }
        swap(number, i + 1, right);
        return i + 1;
    }

}