数据结构——查找算法

查找在实际的应用开发中很常见，所以有必要详细深入的梳理一下。根据查找过程时，是否需要同时插入或删除元素，可分为静态查找和动态查找。

一、静态查找

1.顺序查找
顺序查找又称为线性查找，是一种最简单、最常用的查找方法。

    /**
     * 顺序查找
     * @param a 查找表
     * @param x 查找关键字
     * @return 关键字在查找表中的位置，未找到则返回-1
     */
    public static int sequenceSearch(int a[], int x) {
        if(a != null && a.length > 0) {
            for (int i = 0; i < a.length; i++) {
                if(a[i] == x) {
                    return i;
                }
            }
        }
        return -1;
    }

下面说说顺序查找算法的事件复杂度，如果查找成功，平均的遍历次数为(n+1)/2；如果未找到，则遍历次数为n。顺序查找的优点就是算法简单、应用广泛，并且对表的结构没有任何要求；缺点就是查找效率较低，当数据量较大时，不推荐使用顺序查找。

2.二分查找
二分查找是一种很高效的方法，但前提是需要查找表中的元素必须有序排列，如果要使用该方法，则需要先对查找表中的元素进行排序。
算法思路为，取表(元素按照升序排列)中间元素作为比较对象，如果给定值与中间元素相等，则查找成功；如果给定值比中间元素大，则在中间元素右边的区间继续查找；如果给定值比中间元素小，则在中间元素左边的区间继续查找，以此类推，具体的实现过程如下：

    /**
     * 二分查找算法   
     * @param a 查找表
     * @param x 查找关键字
     * @return 关键字在查找表中的位置，未找到则返回-1
     */
    public static int binarySearch(int a[], int x) {
        if(a != null && a.length > 0) {
            int low = 0;
            int high = a.length;
            int mid = 0;
            while (low < high) {
                mid = (high + low)/2;
                if(a[mid] == x) {
                    return mid;
                }else if (a[mid] > x) {
                    high = mid - 1;
                }else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }

二分查找的效率较高，具体的时间复杂度为log2(n)，也就是说8个元素中，只需要查找3次就可以知道结果(包括查找成功和未找到)。

3.斐波那契查找
需要介绍一下黄金分割比例，是指事物各部分之间存在着一定的数学关系。将事物一分为二，较大部分与较小部分之比等于整体与较大部分之比，比值为1:0.618或者1.618:1。
还需要介绍斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金分割比例运用到查找技术中。
斐波那契查找是在二分查找的基础上进行优化，查找表必须是有序排列。
算法思路：

4.插值查找
5.分块查找

二、动态查找

1.二叉排序树
2.平衡二叉树