查找--有序表查找(折半查找，插值查找，斐波拉契查找)

版权声明：本文源自简书tianma，转载请务必注明出处：http://www.jianshu.com/p/a3bda7ba96ea

引言
如果待查找的数组是有序的，那么此时的查找就是有序表查找，这对于查找的帮助是很大的。属于有序表查找的有：折半查找（二分查找）、插值查找以及斐波那契查找。

1. 折半查找
折半查找又称为二分查找，是一种效率较高的查找算法。折半查找的先决条件是查找表中的数据元素排列必须是有序的。折半查找先以有序数列的中点位置为比较对象，如果要找的元素值小于中点位置元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，可以将查找的区间缩小一半，每次比较，都可以将当前查找范围缩小至一般，可以明显的减少比较的次数，提高查找效率。
时间复杂度：O(logn)
算法实现：

// 定义接口
interface Searcher {
    /**
     * 从数组array中查找关键字key,如果存在则返回该关键字在数组中任意出现的位置(不局限于首次或者末次之类的),否则返回-1
     */
    int search(int[] array, int key);
}

/**
 * 二分法查找,时间复杂度O(logn)
 */
class BinarySearcher implements Searcher {
    // 二分法查找前提,查找表array是顺序(这里要求递增)排列的
    @Override
    public int search(int[] array, int key) {
        int low, high, mid;
        low = 0; // 定义最低下标为array首位
        high = array.length - 1; // 定义最高下标为array末位
        while (low <= high) {
            mid = (low + high) / 2; // 折半
            if (array[mid] > key) {
                // 中值比key大,则high=mid-1
                high = mid - 1;
            } else if (array[mid] < key) {
                // 中值比key小,则low=mid+1
                low = mid + 1;
            } else {
                // 相等说明mid即为key在array中所在位置
                return mid;
            }
        }
        return -1;
    }
}

2. 插值查找
插值查找是二分查找演化而来，相比于二分查找(折半),该算法考虑的是每次折的时候折多少,即不一定是1/2;如在一本字典中找"abstract"这个单词,我们自己来操作肯定是先翻到字典开始的那一小部分,而不是从字典的中间开始进行折半查找。

在二分查找中mid=(low+high)/2=low+1/2*(high-low),插值查找就是对1/2(系数,或者说比例)进行改变，它将1/2变成 (key - array[low])/(array[high] - array[low]),其实就是计算线性比例。

时间复杂度：O(logn)
因为插值查找是依赖线性比例的，如果当前数组分布不是均匀的，那么该算法就不合适。

算法实现：

class InterpolateSearcher implements Searcher {

    @Override
    public int search(int[] array, int key) {
        int low, high, mid;
        low = 0; // 定义最低下标为array首位
        high = array.length - 1; // 定义最高下标为array末位
        while (low <= high) {
            // 相比二分法查找的更改处
            mid = low + (int) (1.0 * (key - array[low]) / (array[high] - array[low]) * (high - low));
            if (array[mid] > key) {
                // 中值比key大,则high=mid-1
                high = mid - 1;
            } else if (array[mid] < key) {
                // 中值比key小,则low=mid+1
                low = mid + 1;
            } else {
                // 相等说明mid即为key在array中所在位置
                return mid;
            }
        }
        return -1;
    }
}

3. 斐波那契查找
根据前面二分查找以及插值查找来看，有序表上的查找的关键就是如何分割当前查找的区域（二分查找对半分割，差值查找按线性比例分割），说到分割，还有一个著名的分割方式就是黄金分割。

斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、····，在数学上，斐波那契被递归方法如下定义：F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2）。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）

所以我们可以根据斐波那契数列对当前区域进行分割 :)

查找算法：在斐波那契数列找一个等于略大于查找表中元素个数的数F(n)，将原查找表扩展为长度为F(n)(如果要补充元素，则补充重复最后一个元素，直到满足数组元素个数为F(n)个元素)，完成后进行斐波那契分割，即F(n)个元素分割为前半部分F(n-1)个元素，后半部分F(n-2)个元素，找出要查找的元素在那一部分并递归，直到找到。
时间复杂度：O(logn)，平均性能优于二分查找。
算法实现：

class FibonacciSearcher implements Searcher {

    private static final int MAX_ARRAY_SIZE = 30;

    /**
     * 得到长度为len的斐波那契数列
     * 
     * @return
     */
    private int[] fibonacci(int len) {
        if (len < 0)
            throw new IllegalArgumentException("length must bigger than 0");
        int[] fibonacci = new int[len];
        fibonacci[0] = 1;
        fibonacci[1] = 1;
        for (int i = 2; i < len; i++) {
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        }
        return fibonacci;
    }

    @Override
    public int search(int[] array, int key) {
        int low = 0; // 低位
        int len = array.length;
        int high = len - 1; // 高位
        int mid; // 中间位
        int k = 0; // 斐波那契数列下标(用于进行分割)
        // 获取斐波那契数列
        int[] fib = fibonacci(MAX_ARRAY_SIZE);
        // 获取斐波那契数列分割点位置
        while (len > fib[k] - 1) {
            k++;
        }
        // 创建临时数组(数组长度为fib[k] - 1)
        int[] tmp = new int[fib[k] - 1];
        // 拷贝原数组到tmp数组中
        System.arraycopy(array, 0, tmp, 0, len);
        // 填充tmp数组中剩余的位置,补充的元素值为最后一个元素值
        for (int i = len; i < fib[k] - 1; i++) {
            tmp[i] = array[high];
        }

        // 开始进行类似于二分查找的查找
        while (low <= high) {
            // 对于tmp数组,整个数组的长度为fib[k]-1
            // 而 fib[k]-1 = (fib[k-1]-1) + 1 + (fib[k-2]-1);
            // 所以可以这样理解： mid下标对应元素可以将整个数组拆分为两部分,第1部分有fib[k-1]-1个元素,第2部分有fib[k-2]-1个元素
            // mid=low+fib[k-1]-1; 正是将 数组的[low, max(high,tmp.length-1)]
            // 部分按照斐波那契规则分为两部分
            mid = low + fib[k - 1] - 1;
            if (tmp[mid] > key) {
                // 需要查找第1部分
                high = mid - 1;
                // fib[k] = fib[k-1] + fib[k-2]
                // 第一部分有fib[k-1]个元素,所以将k-1赋值为k
                k = k - 1;
            } else if (tmp[mid] < key) {
                // 需要查找第2部分
                low = mid + 1;
                // fib[k] = fib[k-1] + fib[k-2]
                // 第二部分有fib[k-2]个元素,所以将k-2赋值给k
                k = k - 2;
            } else {
                // 查找成功
                // 以下代码其实就是返回 min(mid, high);
                // return Math.min(mid, high);
                if (mid <= high)
                    return mid;
                else
                    return high; // 因为mid可能大于high,即查找到了补充的元素,那么还是应该返回high
            }
        }
        return -1;
    }
}

结束语
以上三种查找算法中，都依赖于顺序表，三者的区别本质上就是分割点选的不同。在分割点的选择中，折半查找 mid=(low+high)/2是加法与除法运算；插值查找mid = low+(key-array[low])/(array[high]-array[low])*(high-low)是复杂的四则运算；斐波那契查找mid=low+fib[k-1]-1是简单的加减运算。在海量数据查找过程中细微的差别会影响最终的效率。

三种查找算法，各有优劣，实际开发可以根据数据的特点综合考虑再做出选择。