原文作者:Poll的笔记
来源:博客园
链接:http://www.cnblogs.com/maybe2030/p/4715035.html#top
查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法,说是七种,其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。
查找定义:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。
查找算法分类:
1)静态查找和动态查找;
注:静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
2)无序查找和有序查找。
无序查找:被查找数列有序无序均可; 有序查找:被查找数列必须为有序数列。
平均查找长度(Average Search Length,ASL):需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。
对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL = Pi*Ci的和。
Pi:查找表中第i个数据元素的概率。
Ci:找到第i个数据元素时已经比较过的次数。
说明:顺序查找适合于存储结构为顺序存储或链接存储的线性表。
基本思想:顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。
复杂度分析: 查找成功时的平均查找长度为:(假设每个数据元素的概率相等) ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
当查找不成功时,需要n次比较,时间复杂度为O(n);
所以,顺序查找的时间复杂度为O(n)。
C++实现源码:
//顺序查找
int SequenceSearch(int a[], int value, int n)
{int i;for(i=0; i
说明:元素必须是有序的,如果是无序的则要先进行排序操作。
基本思想:也称为是折半查找,属于有序查找算法。用给定值k先与中间结点的关键字比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归进行,直到查找到或查找结束发现表中没有这样的结点。
复杂度分析:最坏情况下,关键词比较次数为
折半查找是一棵二叉排序树,每个根结点的值都大于左子树的所有结点的值,小于右子树所有结点的值。
例如:长度为10的有序表的平均查找长度为:ASL=(1*1+2*2+3*4+4*3)/10=29/10=2.9;
注:折半查找的前提条件是需要有序表顺序存储(即顺序表),对于静态查找表,一次排序后不再变化,折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说,维护有序的排序会带来不小的工作量,那就不建议使用。——《大话数据结构》
C++实现源码:
//二分查找(折半查找),循环实现
int BinarySearch1(int a[], int value, int n)
{int low, high, mid;low &#61; 0;high &#61; n-1;while(low<&#61;high){mid &#61; (low&#43;high)/2;if(a[mid]&#61;&#61;value)return mid;else if(a[mid]>value)high &#61; mid-1;else if(a[mid]
int BinarySearch2(int a[], int value, int low, int high)
{if(low <&#61; high){int mid &#61; low&#43;(high-low)/2;if(a[mid]&#61;&#61;value)return mid;else if(a[mid]>value)return BinarySearch2(a, value, low, mid-1);else if(a[mid]
在介绍插值查找之前&#xff0c;首先考虑一个新问题&#xff0c;为什么上述算法一定要是折半&#xff0c;而不是折四分之一或者折更多呢&#xff1f;打个比方&#xff0c;在英文字典里面查“apple”&#xff0c;你下意识翻开字典是翻前面的书页还是后面的书页呢&#xff1f;如果再让你查“zoo”&#xff0c;你又怎么查&#xff1f;很显然&#xff0c;这里你绝对不会是从中间开始查起&#xff0c;而是有一定目的的往前或往后翻。
同样的&#xff0c;比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5&#xff0c; 我们自然会考虑从数组下标较小的开始查找。
经过以上分析&#xff0c;折半查找这种查找方式&#xff0c;不是自适应的&#xff08;也就是说是傻瓜式的&#xff09;。二分查找中查找点计算如下&#xff1a;
mid&#61;(low&#43;high)/2, 即mid&#61;low&#43;1/2*(high-low);
通过类比&#xff0c;我们可以将查找的点改进为如下&#xff1a;
mid&#61;low&#43;(key-a[low])/(a[high]-a[low])*(high-low)
也就是将上述的比例参数1/2改进为自适应的&#xff0c;根据关键字在整个有序表中所处的位置&#xff0c;让mid值的变化更靠近关键字key&#xff0c;这样也就间接地减少了比较次数。
基本思想&#xff1a;基于二分查找算法&#xff0c;将查找点的选择改进为自适应选择&#xff0c;可以提高查找效率。当然&#xff0c;差值查找也属于有序查找。
注&#xff1a;对于表长较大&#xff0c;而关键字分布又比较均匀的查找表来说&#xff0c;插值查找算法的平均性能比折半查找要好的多。反之&#xff0c;数组中如果分布非常不均匀&#xff0c;那么插值查找未必是很合适的选择。
复杂度分析&#xff1a;查找成功或者失败的时间复杂度均为
。C&#43;&#43;实现源码&#xff1a;
//插值查找
int InsertionSearch(int a[], int value, int low, int high)
{if(low <&#61; high){int mid &#61; low&#43;(value-a[low])/(a[high]-a[low])*(high-low);if(a[mid]&#61;&#61;value)return mid;if(a[mid]>value)return InsertionSearch(a, value, low, mid-1);if(a[mid]
在介绍斐波那契查找算法之前&#xff0c;我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。
黄金比例又称黄金分割&#xff0c;是指事物各部分间一定的数学比例关系&#xff0c;即将整体一分为二&#xff0c;较大部分与较小部分之比等于整体与较大部分之比&#xff0c;其比值约为1:0.618或1.618:1。
0.618被公认为最具有审美意义的比例数字&#xff0c;这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域&#xff0c;而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。
大家记不记得斐波那契数列&#xff1a;1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….&#xff08;从第三个数开始&#xff0c;后边每一个数都是前两个数的和&#xff09;。然后我们会发现&#xff0c;随着斐波那契数列的递增&#xff0c;前后两个数的比值会越来越接近0.618&#xff0c;利用这个特性&#xff0c;我们就可以将黄金比例运用到查找技术中。
基本思想&#xff1a;也是二分查找的一种提升算法&#xff0c;通过运用黄金比例的概念在数列中选择查找点进行查找&#xff0c;提高查找效率。同样地&#xff0c;斐波那契查找也属于一种有序查找算法。
相对于折半查找&#xff0c;一般将待比较的key值与第mid&#61;&#xff08;low&#43;high&#xff09;/2位置的元素比较&#xff0c;比较结果分三种情况&#xff1a;
1&#xff09;相等&#xff0c;mid位置的元素即为所求&#xff1b;
2&#xff09;>&#xff0c;low&#61;mid&#43;1&#xff1b;
3&#xff09;<&#xff0c;high&#61;mid-1。
斐波那契查找与折半查找很相似&#xff0c;他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1&#xff0c;及n&#61;F(k)-1;
开始将k值与第F(k-1)位置的记录进行比较(及mid&#61;low&#43;F(k-1)-1),比较结果也分为三种&#xff1a;
1&#xff09;相等&#xff0c;mid位置的元素即为所求&#xff1b;
2&#xff09;>&#xff0c;low&#61;mid&#43;1,k-&#61;2;
说明&#xff1a;low&#61;mid&#43;1说明待查找的元素在[mid&#43;1,high]范围内&#xff0c;k-&#61;2 说明范围[mid&#43;1,high]内的元素个数为n-(F(k-1))&#61; Fk-1-F(k-1)&#61;Fk-F(k-1)-1&#61;F(k-2)-1个&#xff0c;所以可以递归的应用斐波那契查找。
3&#xff09;<&#xff0c;high&#61;mid-1,k-&#61;1。
说明&#xff1a;low&#61;mid&#43;1说明待查找的元素在[low,mid-1]范围内&#xff0c;k-&#61;1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个&#xff0c;所以可以递归 的应用斐波那契查找。
复杂度分析&#xff1a;最坏情况下&#xff0c;时间复杂度为
&#xff0c;且其期望复杂度也为 。C&#43;&#43;实现源码&#xff1a;
#include
#include
using namespace std;const int max_size&#61;20; //斐波那契数组的长度
/*构造一个斐波那契数组*/
void Fibonacci(int * F){F[0]&#61;0;F[1]&#61;1;for(int i&#61;2;i
//a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
int FibonacciSearch(int *a, int n, int key){int low&#61;0;int high&#61;n-1;int F[max_size];Fibonacci(F);//构造一个斐波那契数组Fint k&#61;0;while(n>F[k]-1)//计算n位于斐波那契数列的位置&#43;&#43;k;int *temp;//将数组a扩展到F[k]-1的长度temp&#61;new int [F[k]-1];memcpy(temp, a, n*sizeof(int));for(int i&#61;n;i
}void test(){int a[] &#61; {0,16,24,35,47,59,62,73,88,99};int key &#61; 100;int index &#61; FibonacciSearch(a, sizeof(a)/sizeof(int), key);cout <
}
基本思想&#xff1a;二叉查找树是先对待查找的数据进行生成树&#xff0c;确保树的左分支的值小于右分支的值&#xff0c;然后在就行和每个节点的父节点比较大小&#xff0c;查找最适合的范围。 这个算法的查找效率很高&#xff0c;但是如果使用这种查找方法要首先创建树。
二叉查找树&#xff08;BinarySearch Tree&#xff0c;也叫二叉搜索树&#xff0c;或称二叉排序树Binary Sort Tree&#xff09;或者是一棵空树&#xff0c;或者是具有下列性质的二叉树&#xff1a;
1&#xff09;若任意节点的左子树不空&#xff0c;则左子树上所有结点的值均小于它的根结点的值&#xff1b;
2&#xff09;若任意节点的右子树不空&#xff0c;则右子树上所有结点的值均大于它的根结点的值&#xff1b;
3&#xff09;任意节点的左、右子树也分别为二叉查找树。
二叉查找树性质&#xff1a;对二叉查找树进行中序遍历&#xff0c;即可得到有序的数列。
不同形态的二叉查找树如下图所示&#xff1a;
有关二叉查找树的查找、插入、删除等操作的详细讲解&#xff0c;请移步浅谈算法和数据结构: 七 二叉查找树。
复杂度分析&#xff1a;它和二分查找一样&#xff0c;插入和查找的时间复杂度均为
&#xff0c;但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候&#xff0c;树没有保持平衡&#xff08;比如&#xff0c;我们查找上图&#xff08;b&#xff09;中的“17”&#xff0c;我们需要进行n次查找操作&#xff09;。我们追求的是在最坏的情况下仍然有较好的时间复杂度&#xff0c;这就是平衡查找树设计的初衷。下图为二叉树查找和顺序查找以及二分查找性能的对比图&#xff1a;
基于二叉查找树进行优化&#xff0c;进而可以得到其他的树表查找算法&#xff0c;如平衡树、红黑树等高效算法。
2-3查找树定义&#xff1a;和二叉树不一样&#xff0c;2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)&#xff0c;他保存1个key和左右两个自己点。对应3节点(3-node)&#xff0c;保存两个Key&#xff0c;2-3查找树的定义如下&#xff1a;
1&#xff09;要么为空&#xff0c;要么&#xff08;这个怎么解释&#xff1f;&#xff09;
2&#xff09;对于2节点&#xff0c;该节点保存一个key及对应value&#xff0c;以及两个指向左右节点的节点&#xff0c;左节点也是一个2-3节点&#xff0c;所有的值都比key要小&#xff0c;右节点也是一个2-3节点&#xff0c;所有的值比key要大。
3&#xff09;对于3节点&#xff0c;该节点保存两个key及对应value&#xff0c;以及三个指向左中右的节点。左节点也是一个2-3节点&#xff0c;所有的值均比两个key中的最小的key还要小&#xff1b;中间节点也是一个2-3节点&#xff0c;中间节点的key值在两个根节点key值之间&#xff1b;右节点也是一个2-3节点&#xff0c;节点的所有key值比两个key中的最大的key还要大。
性质1&#xff1a;
1&#xff09;如果中序遍历2-3查找树&#xff0c;就可以得到排好序的序列&#xff1b;
2&#xff09;在一个完全平衡的2-3查找树中&#xff0c;根节点到每一个为空节点的距离都相同。&#xff08;这也是平衡树中“平衡”一词的概念&#xff0c;根节点到叶节点的最长距离对应于查找算法的最坏情况&#xff0c;而平衡树中根节点到叶节点的距离都一样&#xff0c;最坏情况也具有对数复杂度。&#xff09;
性质2&#xff1a;
如下图所示&#xff1a;
复杂度分析&#xff1a;
2-3树的查找效率与树的高度是息息相关的。
距离来说&#xff0c;对于1百万个节点的2-3树&#xff0c;树的高度为12-20之间&#xff0c;对于10亿个节点的2-3树&#xff0c;树的高度为18-30之间。
对于插入来说&#xff0c;只需要常数次操作即可完成&#xff0c;因为他只需要修改与该节点关联的节点即可&#xff0c;不需要检查其他节点&#xff0c;所以效率和查找类似。下面是2-3查找树的效率&#xff1a;
2-3查找树能保证在插入元素之后能保持树的平衡状态&#xff0c;最坏情况下即所有的子节点都是2-node&#xff0c;树的高度为
基本思想&#xff1a;红黑树的思想就是对2-3查找树进行编码&#xff0c;尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型&#xff0c;红色链接&#xff0c;他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的&#xff0c;使用红色链接的两个2-nodes来表示一个3-nodes节点&#xff0c;并且向左倾斜&#xff0c;即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改&#xff0c;和普通的二叉查找树相同。
红黑树的定义&#xff1a;
红黑树是一种具有红色和黑色链接的平衡查找树&#xff0c;同时满足&#xff1a;
下图可以看到红黑树其实是2-3树的另外一种表现形式&#xff1a;如果我们将红色的连线水平绘制&#xff0c;那么他链接的两个2-node节点就是2-3树中的一个3-node节点了。
红黑树的性质&#xff1a;整个树完全黑色平衡&#xff0c;即从根节点到所有叶子结点的路径上&#xff0c;黑色链接的个数都相同&#xff08;2-3树的第2&#xff09;性质&#xff0c;从根节点到叶子节点的距离都相等&#xff09;。
复杂度分析&#xff1a;最坏的情况就是&#xff0c;红黑树中除了最左侧路径全部是由3-node节点组成&#xff0c;即红黑相间的路径长度是全黑路径长度的2倍。
下图是一个典型的红黑树&#xff0c;从中可以看到最长的路径(红黑相间的路径)是最短路径的2倍&#xff1a;
红黑树的平均高度大约为
。下图是红黑树在各种情况下的时间复杂度&#xff0c;可以看出红黑树是2-3查找树的一种实现&#xff0c;它能保证最坏情况下仍然具有对数的时间复杂度。
红黑树这种数据结构应用十分广泛&#xff0c;在多种编程语言中被用作符号表的实现&#xff0c;如&#xff1a;
平衡查找树中的2-3树以及其实现红黑树的2-3树中&#xff0c;一个节点最多有2个key&#xff0c;而红黑树则使用染色的方式来标识这两个key。
维基百科对B树的定义为“在计算机科学中&#xff0c;B树&#xff08;B-tree&#xff09;是一种树状数据结构&#xff0c;它能够存储数据、对其进行排序并允许以
B树定义&#xff1a;
B树可以看作是对2-3查找树的一种扩展&#xff0c;即他允许每个节点有M-1个子节点。
下图是一个M&#61;4 阶的B树:
可以看到B树是2-3树的一种扩展&#xff0c;他允许一个节点有多于2个的元素。B树的插入及平衡化操作和2-3树很相似&#xff0c;这里就不介绍了。下面是往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
的演示动画&#xff08;gif图超过知乎处理范围&#xff0c;放个链接看图吧&#xff09;&#xff1a;
https://files-cdn.cnblogs.com/files/zkfopen/btreebuild.gif
B&#43;树定义&#xff1a;
B&#43;树是对B树的一种变形树&#xff0c;它与B树的差异在于&#xff1a;
如下图&#xff0c;是一个B&#43;树:
下图是B&#43;树的插入动画&#xff08;gif图超过知乎处理范围&#xff0c;放个链接看图吧&#xff09;&#xff1a;
https://files-cdn.cnblogs.com/files/zkfopen/Bplustreebuild.gif
B和B&#43;树的区别在于&#xff0c;B&#43;树的非叶子结点只包含导航信息&#xff0c;不包含实际的值&#xff0c;所有的叶子结点和相连的节点使用链表相连&#xff0c;便于区间查找和遍历。
B&#43; 树的优点在于&#xff1a;
但是B树也有优点&#xff0c;其优点在于&#xff0c;由于B树的每一个节点都包含key和value&#xff0c;因此经常访问的元素可能离根节点更近&#xff0c;因此访问也更迅速。
下面是B 树和B&#43;树的区别图&#xff1a;
B/B&#43;树常用于文件系统和数据库系统中&#xff0c;它通过对每个节点存储个数的扩展&#xff0c;使得对连续的数据能够进行较快的定位和访问&#xff0c;能够有效减少查找时间&#xff0c;提高存储的空间局部性从而减少IO操作。它广泛用于文件系统及数据库中&#xff0c;如&#xff1a;
有关B/B&#43;树在数据库索引中的应用&#xff0c;请看张洋的MySQL索引背后的数据结构及算法原理这篇文章&#xff0c;这篇文章对MySQL中的如何使用B&#43;树进行索引有比较详细的介绍&#xff0c;推荐阅读。
二叉查找树平均查找性能不错&#xff0c;为
除此之外&#xff0c;2-3查找树的另一个扩展——B/B&#43;平衡树&#xff0c;在文件系统和数据库系统中有着广泛的应用。
分块查找又称索引顺序查找&#xff0c;它是顺序查找的一种改进方法。
算法思想&#xff1a;将n个数据元素"按块有序"划分为m块&#xff08;m ≤ n&#xff09;。每一块中的结点不必有序&#xff0c;但块与块之间必须"按块有序"&#xff1b;即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字&#xff1b;而第2块中任一元素又都必须小于第3块中的任一元素&#xff0c;……
算法流程&#xff1a;
step1 先选取各块中的最大关键字构成一个索引表&#xff1b;
step2 查找分两个部分&#xff1a;先对索引表进行二分查找或顺序查找&#xff0c;以确定待查记录在哪一块中&#xff1b;然后&#xff0c;在已确定的块中用顺序法进行查找。
什么是哈希表&#xff08;Hash&#xff09;&#xff1f;
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数&#xff08;哈希函数&#xff0c; 也叫做散列函数&#xff09;&#xff0c;使得每个元素的关键字都与一个函数值&#xff08;即数组下标&#xff09;相对应&#xff0c;于是用这个数组单元来存储这个元素&#xff1b;也可以简单的理解为&#xff0c;按照关键字为每一个元素"分类"&#xff0c;然后将这个元素存储在相应"类"所对应的地方。但是&#xff0c;不能够保证每个元素的关键字与函数值是一一对应的&#xff0c;因此极有可能出现对于不同的元素&#xff0c;却计算出了相同的函数值&#xff0c;这样就产生了"冲突"&#xff0c;换句话说&#xff0c;就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说&#xff0c;"直接定址"与"解决冲突"是哈希表的两大特点。
什么是哈希函数&#xff1f;
哈希函数的规则是&#xff1a;通过某种转换关系&#xff0c;使关键字适度的分散到指定大小的的顺序结构中&#xff0c;越分散&#xff0c;则以后查找的时间复杂度越小&#xff0c;空间复杂度越高。
算法思想&#xff1a;哈希的思路很简单&#xff0c;如果所有的键都是整数&#xff0c;那么就可以使用一个简单的无序数组来实现&#xff1a;将键作为索引&#xff0c;值即为其对应的值&#xff0c;这样就可以快速访问任意键的值。这是对于简单的键的情况&#xff0c;我们将其扩展到可以处理更加复杂的类型的键。
算法流程&#xff1a;
1&#xff09;用给定的哈希函数构造哈希表&#xff1b;
2&#xff09;根据选择的冲突处理方法解决地址冲突&#xff1b;
常见的解决冲突的方法&#xff1a;拉链法和线性探测法。详细的介绍可以参见&#xff1a;浅谈算法和数据结构: 十一 哈希表。
3&#xff09;在哈希表的基础上执行哈希查找。
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制&#xff0c;那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)&#xff1b;如果没有时间限制&#xff0c;那么我们可以使用无序数组并进行顺序查找&#xff0c;这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。
复杂度分析&#xff1a;
单纯论查找复杂度&#xff1a;对于无冲突的Hash表而言&#xff0c;查找复杂度为O(1)&#xff08;注意&#xff0c;在查找之前我们需要构建相应的Hash表&#xff09;。
使用Hash&#xff0c;我们付出了什么&#xff1f;
我们在实际编程中存储一个大规模的数据&#xff0c;最先想到的存储结构可能就是map&#xff0c;也就是我们常说的KV pair&#xff0c;经常使用Python的博友可能更有这种体会。使用map的好处就是&#xff0c;我们在后续处理数据处理时&#xff0c;可以根据数据的key快速的查找到对应的value值。map的本质就是Hash表&#xff0c;那我们在获取了超高查找效率的基础上&#xff0c;我们付出了什么&#xff1f;
Hash是一种典型 以空间换时间 的算法&#xff0c;比如原来一个长度为100的数组&#xff0c;对其查找&#xff0c;只需要遍历且匹配相应记录即可&#xff0c;从空间复杂度上来看&#xff0c;假如数组存储的是byte类型数据&#xff0c;那么该数组占用100byte空间。现在我们采用Hash算法&#xff0c;我们前面说的Hash必须有一个规则&#xff0c;约束键与存储位置的关系&#xff0c;那么就需要一个固定长度的hash表&#xff0c;此时&#xff0c;仍然是100byte的数组&#xff0c;假设我们需要的100byte用来记录键与位置的关系&#xff0c;那么总的空间为200byte,而且用于记录规则的表大小会根据规则&#xff0c;大小可能是不定的。
Hash算法和其他查找算法的性能对比&#xff1a;
关于哈希表的构造及冲突解决方法可以参见&#xff1a;哈希表