查找算法

查找算法

查找是在大量的信息中寻找一个特定的元素，在计算机当中，查找是常用的基本运算。

查找定义: 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。

查找算法分类：

• 静态查找和动态查找

*   静态或者动态都是对查找表而言的。动态表查找表中有删除和插入操作的表。

• 无序查找和有序查找

*   无序查找:被查找数列有序无序均可。
    
    
*   有序查找:被查找数列必须有序数列。

平均查找长度: 需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

对于含有N个数据元素的查找表。查找成功的平均查找长度为：ASL=Pi*CI的和。

• PI: 查找表中第i个数据元素的概率。

• CI：找到第i个数据元素时已经比较过的次数。

顺序查找

说明:顺序查找适合于存储结构为顺序存储或链接存储的线性表。

基本思想：顺序查找也称为线性查找。属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的节点关键字与给定值k相比较。若相等则表示查找成功。若扫描结束仍没有找到关键字等于K的节点，表示查找失败。

复杂度分析:查找成功时的平均查找长度为ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;

当查找不成功时，需要n+1次比较，时间复杂度为O(n);

二分查找

元素必须时有序的，如果时无序的需要先进行排序操作

基本思想:也称为折半查找，属于有序查找算法。用给定值k先与中间节点的关键字比较，中间节点把线形表分成两个子表，若相等则查找成功；若不想等，再根据k与该中间节点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的节点。

复杂度分析:最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log****2n)；

插值查找

基于二分查找算法，将查找点的选择改进为自适应选择，提高查找效率，该查找算法也属于有序查找。

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

斐波那契查找

斐波那契数列基于二分查找一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查询效率。同样地，斐波那契查找也属于一种有序查找算法。

黄金比例:

黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。

树表查找

二叉树查找算法

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

二叉查找树: 或者是一颗空树，或者是具有以下性质的二叉树:

• 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值。

• 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值

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

复杂度分析:

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

下图为二叉树查找和顺序查找以及二分查找性能的对比图：

[图片上传失败...(image-9a7735-1629635619410)]

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

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

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

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

[图片上传失败...(image-d8043a-1629635619410)]

2-3查找树的性质

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

2. 在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。

复杂度分析:

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

• 在最坏的情况下，也就是所有的节点都是2-node节点，查找效率为lgN

• 在最好的情况下，所有的节点都是3-node节点，查找效率为log3N约等于0.631lgN

平衡查找树之红黑树

2-3查找树能保证在插入元素之后能保持树的平衡，最坏情况即所有的子节点都是2-node，树的高度为lgn。从而保证最坏情况瞎的时间复杂度。

基本思想:红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，它用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。

红黑树的特点

• 节点时红色或者黑色

• 根节点时黑色

• 每个叶子的节点都是黑色的空节点

• 从任意节点到其每个叶子的所有路径都包含相同的黑色节点

红黑树的性质:整个树完全黑色平衡，即从根节点到到所有叶子结点的路径上，黑色链接的个数都相同。

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

[图片上传失败...(image-2471e7-1629635619410)]

红黑树的平均高度大学为logn。对于应用场景 如java中的TreeMap、TreeSet等 都是红黑树的应用。

B树和B+数

B树是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。

B树:

• 根节点至少有两个子节点

• 每个节点有M-1个key，并且以升序排列

• 位于M-1和M key的子节点的值位于M-1和M key对应的Value之间

• 其它节点至少有M/2个子节点。

B+树定义

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

• 有K个子结点的结点必然有K个关键码

• 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。

• 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

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

B+树的优点在于

• 由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。

• B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。

B树的优点在于，由于B树的每一个结点都包含key和value，因此经常访问的元素可能离根结点更近，因此访问页更速度。

B/B+树应用场景: ORACLE，MYSQL,SQLSERVER等中。

树表查找总结：

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

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

分块查找

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

算法思想: 将N个数据元素"按块有序"划分为m块(m=<n)。每一块中的结点不必有序，但块玉块之间必须按块有序；即第一块中任何一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素。

算法流程

1. 先选取各块中的最大关键字构成一个索引表
2. 查找分为2个部分；先对索引表二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序方法进行查找。

哈希查找

什么是哈希表?

哈希表可以以极快的速度来查找、添加或删除元素（只需要数次的比较操作。）它比红黑树、二叉搜索树都要快得多。但是哈希表没有排序功能，类似的，如寻找最大值、最小值、中值这些行为都不能在哈希表中实现。

什么是hash函数?

哈希函数的规则是:通过某种转换关系，使关键字适度的分散到指定大小的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高

算法思想:哈希的思路很简单，如果所有的键都是证书，那么就可以使用一个简单的无序数组来实现；将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。

算法流程

1. 用给定的哈希函数构造哈希表。
2. 根据选择的冲突处理方法解决地址冲突。
   1. 常见的解决冲突的方法:拉链法和线性探测法。
3. 在哈希表的基础上执行哈希查找。

哈希表是一个在时间和空间做出权衡的经典例子，如果内存没有限制，那么可以直接将键作为数组的索引。如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存

复杂度分析

单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1);

使用Hash，我们付出了什么？

Hash是一种典型以空间换时间的算法，比如原来一个长度为100的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是byte类型数据，那么该数组占用100byte空间。现在我们采用Hash算法，我们前面说的Hash必须有一个规则，约束键与存储位置的关系，那么就需要一个固定长度的hash表，此时，仍然是100byte的数组，假设我们需要的100byte用来记录键与位置的关系，那么总的空间为200byte,而且用于记录规则的表大小会根据规则，大小可能是不定的。

Hash算法和其他查找算法的性能对比：

hash性能比较