查找算法最强总结及其算法实现 _查找算法

文章插图

在这里插入图片描述
前言本文总结了常用的查找算法，内容包括：

查找算法的定义和思路，动画演示
查找算法的代码实现：Python和JAVA
查找算法性能分析：时间空间复杂度分析
不同排序算法最佳使用场景

面试知识点复习手册此文属于知识点复习手册专栏内容，你还可以通过以下两种途径查看全复习手册文章导航：

关注我的公众号：Rude3Knife 点击公众号下方：技术推文——面试冲刺
全复习手册文章导航(CSDN)

-----正文开始-----预备知识查找算法分类
1）静态查找和动态查找；
注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
2）无序查找和有序查找。

无序查找：被查找数列有序无序均可；
有序查找：被查找数列必须为有序数列。

平均查找长度（Average Search Length，ASL）
需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。
对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。
Pi：查找表中第i个数据元素的概率。
Ci：找到第i个数据元素时已经比较过的次数。
查找性能
从快到慢：

顺序查找，时间复杂度O(N),
分块查找，时间复杂度O(logN+N/m);
二分查找，时间复杂度O(logN)
Fibonacci查找，时间复杂度O(logN)
差值查找，时间复杂度O(log(logN))
哈希查找，时间复杂度O(1)

查找算法1. 顺序查找
说明：属于有序查找，顺序查找适合于存储结构为顺序存储或链接存储的线性表。
复杂度分析：
查找成功时的平均查找长度为：
（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
当查找不成功时，需要n+1次比较，时间复杂度为O(n);
所以，顺序查找的时间复杂度为O(n) 。
Java实现：
2.二分查找
二分查找经典理解：https://www.zhihu.com/question/36132386/answer/155438728
基本思想：
也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
复杂度分析：
最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；对于一个有1024个元素的数组，在最坏的情况下，二分查找法只需要比较log2n + 1= 11次，而在最坏的情况下线性查找要比较1023次。
注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》
注意点：为什么(low +high) / 2会溢出啊？答：两个很大的int相加的话超出 Integer.MAX_VALUE 了
Java实现：
3.插值查找
通过类比，我们可以将二分查找的点改进为如下：
也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。
基本思想：
基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
复杂度分析：
查找成功或者失败的时间复杂度均为O(log2(log2n)) 。
Java实现：
4. 斐波那契查找
https://blog.csdn.net/zsw12013/article/details/50003505
[图片上传失败…(image-97e793-1551795346605)]
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，n=F(k)-1;
复杂度分析：
最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n) 。
注意：生成的数组长度是f[k]-1而不是f[k]
Java：
Python：