插补搜寻法 比二分搜索更优的搜索算法

说明
如果却搜寻的资料分布平均的话，可以使用插补（Interpolation）搜寻法来进行搜寻，在搜寻
的对象大于500时，插补搜寻法会比二分搜寻法来的快速。
解法
插补搜寻法是以资料分布的近似直线来作比例运算，以求出中间的索引并进行资料比对，如果
取出的值小于要寻找的值，则提高下界，如果取出的值大于要寻找的值，则降低下界，如此不
断的减少搜寻的范围，所以其本原则与二分搜寻法是相同的，至于中间值的寻找是透过比例运
算，如下所示，其中K是指定要寻找的对象， 而m则是可能的索引值：

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

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

public class _44_插补搜寻法 {

    /**
     * @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;
    }

    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, 0, 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 = intsrch(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 intsrch(int[] number, int find) {
        double low, mid, upper;
        low = 0;
        upper = MAX - 1;
        while (low <= upper) {
            mid = (upper - low) * (find - number[(int) low])
             / (number[(int) upper] - number[(int) low]) + low;
            if (mid < low || mid > upper)
                return -1;
            if (find < number[(int) mid])
                upper = mid - 1;
            else if (find > number[(int) mid])
                low = mid + 1;
            else
                return (int) mid;
        }
        return -1;
    }

    /**
     * @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;
    }

}