常用的七大查找算法以及二分查护和插值查找的改进

顺序查找

思想： 从线性表的一端开始逐个扫描比对，如果和目标值相等就返回。属于无序查找算法。
适用于线性表或者链表的存储结构。
代码：

public static int search(int n, int[] nums){
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == n){
                return i;
            }
        }
        return -1;
    }

时间复杂度： $O(n)$O(n)

二分查找

思想： 给定需查找的值key和有序线性表。假定线性表是从小到大排序的。利用折半取中间值的思想，每次都取线性表的中间值和key进行比较；如果中间值大于key，那么去线性表的中间值右端继续进行取中间值比较；如果中间值小于key，那么取线性表的中间值左端的部分继续进行取中间值比较。重复上述步骤直到查找到key。
适用于有序表的查找。
代码：

public static int bs(int key, int nums[]){
        int left = 0;
        int right  = nums.length - 1;
        while (left<right){
            int mid = (left+right)/2;
            if (nums[mid] == key){
                return mid;
            }else if (nums[mid] > key){
                right = mid -1;
            }else {
                left = mid;
            }
        }
        return -1;
    }

时间复杂度： $O(logn)$O(logn)

插值查找

思想： 不同于二分查找每次都是取中间值的操作，插值查找可以根据斜率来拟合数据。因而当数据分布较为均匀的时候，插值搜索算法可以取得更好的效果；但是，如果数据分布是倾斜的，那么利用斜率的思想将不能很好的拟合数据的分布，斜率的重复计算次数就会增加。
插值搜索和二分查找代码上的区别也只有：
二分查找：$mid = (left + right) / 2$mid=(left+right)/2
插值查找：$mid = left + \frac {V[right] - V[left]]}{right - left}(target - V[left])$mid=left+right−leftV[right]−V[left]]​(target−V[left])

代码：

public static int IS(int target, int nums[]){
        int left = 0;
        int right = nums.length - 1;
        while (left < right){
            int mid = left + (right - left)/(nums[right] - nums[left])*(target - nums[left]);
            if (mid == target){
                return mid;
            }else if (mid > target){
                right = mid - 1;
            }else {
                left = mid;
            }
        }
        return  -1;
    }

时间复杂度： $O(log2log2n)$O(log2log2n)

二分查找和插值查找的改进

二分查找的最优算法：
去掉右边界，迭代次数可根据时间复杂度预计算，每次更新的时候只更新左边界。迭代次数完了还没找到的话用顺序查找代替。
伪代码如下：

插值搜索法的改进：
斜率的计算较为耗时，改进斜率计算方法；—重用斜率
利用哨兵机制，及时停止循环；然后再用顺序搜索；
斜率的计算可以用定点运算加速。
伪代码：SIP和TIP

上述的改进方法出自2019年sigmod论文 ，有兴趣的可以去研究。

Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?

斐波那契查找

原理和二分查找基本一样，除了mid值的更新利用了黄金比例分割0.618。略

树表查找

原理是利用树的思想，具体方法可以用二叉树、平衡二叉树、红黑树、B\B+树。
本质都是树查找，需要构建树结构。
原理也比较简单，时间复杂度可以控制在$O(logn)$O(logn)

哈希查找

利用哈希函数进行散列，时间复杂度可达到$O(1)$O(1)。但是会产生碰撞，因此需要对碰撞进行处理。常用的方法有链地址法和线性探测法。java中用的是链地址法。如果链表长度达到8就会分裂成红黑树。哈希查找比骄傲耗费存储空间。

分块查找

分块查找又称索引顺序查找，它是顺序查找的一种改进方法。
　　算法思想：将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……
　　算法流程：
　　- step1 先选取各块中的最大关键字构成一个索引表；
　　- step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。