您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

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

时间:2019-11-05 11:42:30  来源:  作者:
查找算法最强总结及其算法实现

 

在这里插入图片描述

前言

本文总结了常用的查找算法,内容包括:

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

面试知识点复习手册

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

  • 关注我的公众号: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:

5.树表查找

5.1 最简单的树表查找算法——二叉树查找算法

基本思想:

这个算法的查找效率很高,但是如果使用这种查找方法要首先创建树。

二叉查找树(BinarySearch Tree,也叫二叉搜索树,或称二叉排序树Binary Sort Tree)或者是一棵空树,或者是具有下列性质的二叉树:

1)若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

2)若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

3)任意节点的左、右子树也分别为二叉查找树。

二叉查找树性质:

对二叉查找树进行中序遍历,即可得到有序的数列。

有关二叉查找树的查找、插入、删除等操作的详细讲解,请移步浅谈算法和数据结构: 七 二叉查找树

复杂度分析:

它和二分查找一样,插入和查找的时间复杂度均为O(logn),但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候,树没有保持平衡(比如,我们查找上图(b)中的“93”,我们需要进行n次查找操作)。我们追求的是在最坏的情况下仍然有较好的时间复杂度,这就是平衡查找树设计的初衷。

基于二叉查找树进行优化,进而可以得到其他的树表查找算法,如平衡树、红黑树等高效算法。

5.2 平衡查找树之2-3查找树(2-3 Tree)

https://riteme.github.io/blog/2016-3-12/2-3-tree-and-red-black-tree.html

2-3查找树定义:和二叉树不一样,2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node),他保存1个key和左右两个自己点。对应3节点(3-node),保存两个Key,2-3查找树的定义如下:

1)要么为空,要么:

2)对于2节点,该节点保存一个key及对应value,以及两个指向左右节点的节点,左节点也是一个2-3节点,所有的值都比key要小,右节点也是一个2-3节点,所有的值比key要大。

3)对于3节点,该节点保存两个key及对应value,以及三个指向左中右的节点。左节点也是一个2-3节点,所有的值均比两个key中的最小的key还要小;中间节点也是一个2-3节点,中间节点的key值在两个跟节点key值之间;右节点也是一个2-3节点,节点的所有key值比两个key中的最大的key还要大。

2-3查找树的性质:

1)如果中序遍历2-3查找树,就可以得到排好序的序列;

2)在一个完全平衡的2-3查找树中,根节点到每一个为空节点的距离都相同。(这也是平衡树中“平衡”一词的概念,根节点到叶节点的最长距离对应于查找算法的最坏情况,而平衡树中根节点到叶节点的距离都一样,最坏情况也具有对数复杂度。)
复杂度分析:

2-3树的查找效率与树的高度是息息相关的。

距离来说,对于1百万个节点的2-3树,树的高度为12-20之间,对于10亿个节点的2-3树,树的高度为18-30之间。

对于插入来说,只需要常数次操作即可完成,因为他只需要修改与该节点关联的节点即可,不需要检查其他节点,所以效率和查找类似。

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

 

这里写图片描述

5.3 平衡查找树之红黑树(Red-Black Tree)

但是2-3树实现起来比较复杂,于是就有了一种简单实现2-3树的数据结构,即红黑树(Red-Black Tree)。

红黑树的定义:

红黑树是一种具有红色和黑色链接的平衡查找树,同时满足:

  • 红色节点向左倾斜
  • 一个节点不可能有两个红色链接
  • 整个树完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同。

红黑树的性质:整个树完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同(2-3树的第2)性质,从根节点到叶子节点的距离都相等)。

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

 

这里写图片描述

复杂度分析:

最坏的情况就是,红黑树中除了最左侧路径全部是由3-node节点组成,即红黑相间的路径长度是全黑路径长度的2倍。

下图是一个典型的红黑树,从中可以看到最长的路径(红黑相间的路径)是最短路径的2倍:

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

 

这里写图片描述

红黑树这种数据结构应用十分广泛,在多种编程语言中被用作符号表的实现,如:

  • Java中的java.util.TreeMap,java.util.TreeSet;
  • C++ STL中的:map,multimap,multiset;
  • .NET中的:SortedDictionary,SortedSet 等。

5.4 B树和B+树(B Tree/B+ Tree)

普遍运用在数据库和文件系统。

B树可以看作是对2-3查找树的一种扩展,即他允许每个节点有M-1个子节点。

  • 根节点至少有两个子节点
  • 每个节点有M-1个key,并且以升序排列
  • 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
  • 其它节点至少有M/2个子节点

可以看到B树是2-3树的一种扩展,他允许一个节点有多于2个的元素。B树的插入及平衡化操作和2-3树很相似,这里就不介绍了。

下面是往B树中依次插入6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

B+树是对B树的一种变形树,它与B树的差异在于:

  • 有k个子结点的结点必然有k个关键码;
  • 非叶结点仅具有索引作用,跟记录有关的信息均存放在叶结点中。
  • 树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录。

B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。

但是B树也有优点,其优点在于,由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。

  • windows:HPFS文件系统;
  • mac:HFS,HFS+文件系统;
  • linux:ResiserFS,XFS,Ext3FS,JFS文件系统;
  • 数据库:ORACLE,MySQL,SQLSERVER等中。

树表查找总结:

二叉查找树平均查找性能不错,为O(logn),但是最坏情况会退化为O(n)。在二叉查找树的基础上进行优化,我们可以使用平衡查找树。平衡查找树中的2-3查找树,这种数据结构在插入之后能够进行自平衡操作,从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难,红黑树是2-3树的一种简单高效的实现,他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题。红黑树是一种比较高效的平衡查找树,应用非常广泛,很多编程语言的内部实现都或多或少的采用了红黑树。

除此之外,2-3查找树的另一个扩展——B/B+平衡树,在文件系统和数据库系统中有着广泛的应用。

6. 分块查找

解释:https://blog.csdn.net/u013036274/article/details/49176027

属于顺序查找,分块查找又称索引顺序查找,它是顺序查找的一种改进方法。

[图片上传失败…(image-fd2e41-1551795346605)]

算法思想

将n个数据元素"按块有序"划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须"按块有序";即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……

算法流程:

step1 先选取各块中的最大关键字构成一个索引表;

step2 查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。

7.哈希查找

单纯论查找复杂度:对于无冲突的Hash表而言,查找复杂度为O(1)(注意,在查找之前我们需要构建相应的Hash表)。

常见的解决冲突的方法:拉链法和线性探测法。

详细的介绍可以参见:浅谈算法和数据结构: 十一 哈希表。

附录:

Java完整代码,带有测试用例:

主要参考网页

http://www.cnblogs.com/maybe2030/p/4715035.html#_label6



Tags:查找算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除,谢谢。
▌相关推荐
在这里插入图片描述前言本文总结了常用的查找算法,内容包括: 查找算法的定义和思路,动画演示 查找算法的代码实现:Python和Java 查找算法性能分析:时间空间复杂度分析 不同排序...【详细内容】
2019-11-05  Tags: 查找算法  点击:(50)  评论:(0)  加入收藏
用途BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相...【详细内容】
2019-07-01  Tags: 查找算法  点击:(373)  评论:(0)  加入收藏
▌简易百科推荐
架构头条 作者 | theinsaneapp.com译者 | 张健欣策划 | 万佳今天,我们会讨论一些不同的东西,例如 Spotify、YouTube、Signal Messenger、Amazon 等科技巨头的推荐算法,以及像 U...【详细内容】
2021-07-15  技术联盟总坛    Tags:推荐算法   点击:(2)  评论:(0)  加入收藏
说起区块链,似乎大家都懂一点,再往细里一问,似乎又都不懂了。比如,你问一个人:为什么要挖矿,挖的到底是啥。怕是没几个明白人。本文就是要给你讲明白!前言人们一说起区块链,就常常说...【详细内容】
2021-07-13  暖男在奋斗的路上    Tags:加密算法   点击:(6)  评论:(0)  加入收藏
2021年5月26日,极狐阿尔法S 华为HI版正式下线,标志着华为进军自动驾驶迈出关键一步,实现了量产。...【详细内容】
2021-07-08  佐思汽车研究    Tags:自动驾驶算法   点击:(9)  评论:(0)  加入收藏
今天讲的是最有深度的抖音算法机制的剖析,解密平台核心算法机制。主要深度讲下抖音是算法机制到底是怎么工作的,我们的帐号标签原型到底是怎么建立起来的,字节跳动的人工智能AI...【详细内容】
2021-07-05  国阜电商    Tags:抖音平台算法   点击:(11)  评论:(0)  加入收藏
RSA非对称加密RSA是一种常用的非对称加密算法,加密和加密使用不同的密钥,常用于要求安全性较高的加密场景,比如接口的验签和接口数据的加密与解密。与非对称加密算法对比,其安全...【详细内容】
2021-07-04  Java架构学习指南  简书  Tags:接口   点击:(12)  评论:(0)  加入收藏
导读:用户标签是个性化推荐、计算广告、金融征信等众多大数据业务应用的基础,它是原始的用户行为数据和大数据应用之间的桥梁,本文会介绍用户标签的构建方法,也就是用户画像技术...【详细内容】
2021-07-02  华章科技    Tags:用户画像   点击:(16)  评论:(0)  加入收藏
随机红包算法,每个人都有自己的实现思路。package com.jmmq.load.jim.algorithm;import java.math.BigDecimal;import java.util.Arrays;import java.util.List;import java....【详细内容】
2021-07-02  非鸽传书  今日头条  Tags:算法   点击:(10)  评论:(0)  加入收藏
在程序员的实际开发中,哈希算法常常能用得到,本文以哈希算法的原理和应用为核心,和大家详细讲解一下哈希算法的概念、常见算法以及原理、在信息安全的应用等等。 一、概念哈希...【详细内容】
2021-06-25  C语言编程    Tags:哈希算法   点击:(26)  评论:(0)  加入收藏
1. 红黑树1.1 红黑树概述红黑树和我们以前学过的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。不过自从红黑树出来后,AVL...【详细内容】
2021-06-24  Linux天神    Tags:红黑树   点击:(19)  评论:(0)  加入收藏
1. 线性表线性表是一类最简单、最常用的数据结构。简单来说,一个线性表是n个元素的有限序列,其中n≥0,通常表示为(a1,a2,...,an)。其特点是,在非空的数据元素集合中:(1)存在唯一的一个...【详细内容】
2021-06-09  数据人plus  今日头条  Tags:数据结构   点击:(37)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条