常用查找算法总结

查找算法简介

查找（Searching） 就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
查找表（Search Table） 由同一类型的数据元素构成的集合
关键字（Key） 数据元素中某个数据项的值，又称为键值
主键（Primary Key） 可唯一的标识某个数据元素或记录的关键字
常用的查找算法包括：顺序查找、二分查找、哈希表查找、二叉排序树查找

顺序查找

算法简介： 顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。该算法的时间复杂度为O(n)。

基本思路： 从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。

算法实现：

    public int search(int[] nums, int target) {
        if (nums == null || nums.length <= 0) return -1; //首先过滤非法输入的情况
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == target) return i;
        }
        return -1;
    }

算法优点： 算法对查找表中的数据存储没有要求。对于线性链表，只能使用顺序查找。

算法缺点： 是当n很大时，平均查找长度较大，效率低；

二分查找

算法简介：是一种在有序数组中查找某一特定元素的查找算法。查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。即从两端向中间逐步缩小查找的范围。
这种查找算法每一次比较都使查找范围缩小一半。

复杂度分析
时间复杂度：折半搜索每次把搜索区域减少一半，时间复杂度为 O(logn)
空间复杂度：O(1)

代码实现

public int search(int[] nums, int target) {

        int left = 0, right = nums.length-1;
        if (nums.length == 0 || target > nums[right] || target < nums[0]) return -1;
        if (nums.length == 1){
            if (nums[0] == target) return 0;
            else return -1;
        }
        while (right >= left){
            int midle = (right + left) / 2;
            if (nums[midle] == target) return midle;
            if (nums[midle] < target) left = midle+1;
            else if (nums[midle] > target) right = midle-1;
        }

        return -1;
    }

算法优点：每次将查找表缩小一半，时间复杂度为 O(logn)，查找效率高。
算法缺点：要求查找表中的元素必须是有序的。

插值查找

插值查找是在二分查找的基础上进行的改进，二分查找每次将查找的范围缩小一半，即

mid=(low+high) / 2 可以看出，折半查找是一种机械式的查找方式，不是自适应的。因此，在数值分布相对均匀的查找表中， 我们将计算mid的方式改为自适应的查找，即 mid=low+(key-a[low])/(a[high]-a[low])*(high-low) 能够有效提高查找的效率

基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。

适用场景： 插值查找需要在有序表中进行，查找表较长，且关键字的数值分布较为均匀。

复杂度分析：查找成功或者失败的时间复杂度均为O(log2(log2n))

算法优点：对于数值分布均匀的有序查找表，其查找效率明显优于二分查找

算法缺点：对于数值分布不均匀的查找表，其查找效率较差

二叉排序树查找

算法简介：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围
这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。\

算法特点：充分利用了二叉排序树的结构特征进行查找

算法思想：
二叉查找树（BinarySearch Tree）或者是一棵空树，或者是具有下列性质的二叉树： \

1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 任意节点的左、右子树也分别为二叉查找树。

算法复杂度：插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有**O(n)**的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡。