数据结构第七章（一）-顺序查找和折半查找

---

顺序查找和折半查找

---

一、查找

查找就是对比然后找，可能找得到，也可能找不到

查找——在数据集合中寻找满足某种条件的数据元素的过程称为查找

查找表（查找结构）——用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成

概念都比较复杂，其实查找表就是你在什么东西里面查找，这个东西就是查找表。可能是线性结构，也可能是链式存储啥的。

关键字——数据元素中唯一标识钙元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

就是你找的是啥。

注意关键字是唯一标识的哈，比如数据库主键啥的。

对于查找表而言，我们一般进行两种常见操作：

• 查找符合条件的数据元素
• 插入、删除某个数据元素

打比方如果是静态查找表，那我们一般进行的就是第一种，只做查找，所以我们仅关注查找速度即可；如果是动态查找表，除了查找速度，也要关注插入、删除操作是否方便实现。

我们在进行查找的时候，如何评价一个查找算法是好是坏？主要就是看对比的次数多不多，这个对比次数也叫查找长度

查找长度——在查找运算中，需要对比关键字的次数称为查找长度

1.平均查找长度（ASL）

所谓平均查找长度，就是把所有数据元素都查一遍所需要的查找长度再除以数据元素的个数，也就是字面意思，取个平均值。

平均查找长度（ASL，Average Search Length）——所有查找过程中进行关键字的比较次数的平均值

当然这是在默认查找任何一个元素的概率都相同的情况，如果不同就拿各自分别需要查找的次数乘以各自的概率再相加就好了。

举个栗子，比如下面这个二叉排序树：

查找成功的平均查找长度ASL：

ASL=（1 * 1 + 2 * 2 +3 * 4 +4 * 1 ）/ 8 = 2.625

因为查第一层1个元素的要对比一次，查第二层的2个元素要对比两次，查第三层4个元素的要对比3次，查第四层的1各元素要对比4次，所以总共对比次数就是1 * 1 + 2 * 2 +3 * 4 +4 * 1 ，再求个平均就是查找成功的ASL了。

查找失败的平均查找长度ASL：

ASL=（3 * 7 + 4 * 2 ）/ 9 = 3.22

因为查找失败的情况肯定是发现没找到，也就是叶子结点的左右子树的情况，对比3次发现没找到就会落到第三层叶子节点的左右子树上，这一层的情况有7种；对比4次发现没找到第四层叶子结点的左右子树上，这一层的情况有2种，所以所有失败情况总共对比次数就是3 * 7 + 4 * 2，再求个平均就是查找失败的ASL了。

再比如下面这个二叉排序树：

查找成功的平均查找长度ASL：

ASL=（1 * 1 + 2 * 2 +3 * 1 +4 * 1 +5 * 1 +6 * 1 +7 * 1 ）/ 8 = 3.75

这个ASL就比上面那个要多，因为它高度比较深嘛，还是高度比较浅的比较好查。

查找失败的平均查找长度ASL：
ASL = （2 * 3 + 3 + 4 + 5 + 6 + 7 * 2 ）/ 9 = 4.22

这个失败情况也比上面那个对比次数多。

ASL的数量级反映了查找算法时间复杂度

评价一个查找算法的效率时，通常考虑查找成功/查找失败两种情况的ASL

不止有成功还有失败哈

二、顺序查找

顺序查找就是字面意思，意思是一个一个挨个找就vans了。

顺序查找，又叫“线性查找”，通常用于线性表（也可以用于链表）
算法思想，从前往后挨个找，反过来也是一样的

代码更加直观：

typedef struct{     //查找表的数据结构（顺序表）int *elem;      //动态数组基址int tableLen;   //表的长度
}SSTable;//顺序查找
int search_seq(SSTable ST, int  key){int i;for(i = 0; i<ST.tableLen && ST.elem[i] != key; i++){//查找成功，则返回元素下标；查找失败，则返回-1return i==ST.tableLen ? -1 : i;}
}

比如下面这个顺序表：

33	10	13	29	16	19	32	7	43	41	37
0	1	2	3	4	5	6	7	8	9	10	11	12	13	…（下标）

如果要在其中查找“66”，那么就在这个数组内一个一个比对（这个数组的tableLen是11），发现没有和66相等的，也就是指针i为11，此时查找失败，返回-1；如果要在其中查找“43”，发现当 i 等于 8 时刚好找到，所以返回下标8。

1.实现

我们顺序查找的实现，还可以用另一种方法，也就是下标和第几个数对应。但是要这样的话，0下标的位置就空出来了，所以我们可以在位置0处存放“哨兵”，也就是我们需要找的那个数的值。

也就是说，我们的顺序表就变成这样：

66	33	10	13	29	16	19	32	7	43	41	37
0	1	2	3	4	5	6	7	8	9	10	11	12	13	…（下标）

tableLen还是11

数据从下标1开始存

但是我们这回不是从前往后找了，我们从后往前找，看代码比较清晰：

typedef struct{     //查找表的数据结构（顺序表）int *elem;      //动态数组基址int tableLen;   //表的长度
}SSTable;//顺序查找
int search_seq(SSTable ST, int  key){ST.elem[0] = key;   //"哨兵"int i;for(i = ST.tableLen; ST.elem[i] != key; i--){//从后往前找return i;   //查找成功，则返回元素下标；查找失败，则返回0}
}

顺序表里没有的话那就从后往前直到遍历到最前面的0下标，哨兵一定是和自己相等的，所以返回0就是没找到；如果找到了那就返回找到的下标，不是0就是找到了。

那么我们这么做和上面的方法有什么区别呢？其实这样更好，因为上面的我们还要看数组是不是越界，越界就是没找到，这个就不用，因为至少也是有个哨兵是等于它自己的。

添加“哨兵”的优点：无需判断是否越界，效率更高

讲完了算法就要分析它的效率，我们先来看查找成功的ASL

显然就是找1次找到，找2次找到……找n次找到，所以ASL_成功=（1+2+……n）/ n = (n+1)/2

我们再来看查找失败的ASL

查找失败显然就是遍历完发现没有，然后到哨兵，所以要对比 n+1 次，所以 ASL_失败 = n+1

时间复杂度是O(n)

2.算法优化

如果是一个有序表，那我们在表中没有我们要找元素的情况下，就不用再傻乎乎地全部对比完才知道了。比如表中按照从小到大排序，那么我们对比着没找到但发现下一个比它大，就说明后面的也一定找不到了，也就是查找失败了。

打比方我们要在下面这个有序表（查找表中的元素有序存放<递增/递减>）：

7	13	19	29	37	43

我们要在这个表中查找 “21”，当我们从前往后对比到“29”的时候，发现 29>21，就说明查找失败了。

我们可以用一个查找判定树来分析它的ASL，如下图所示：

要想知道查找失败时候的ASL，那就得看上面这个图的长方形的叶子结点，每一个叶子结点对应的都是一种查找失败的情况，比7小啦，比13小啦，比43小啦，比43大啦什么的，所以总共有 n+1 种查找失败的情况（n个结点有n+1个空叶子结点，还记得为什么吗？因为我们在线索二叉树里讲过，每一个结点都有左右两个孩子结点，有2n个孩子结点。所有结点都占一个子结点<除了根节点>，所以只占了n-1个，故剩下的就是没被占的n+1个空叶子结点了。）

第一个叶子结点对比一次，第二个对比两次……最后有两个对比n次的，所以：

ASL_失败=（1+2+3+……+n+n）/ （n+1）= n/2 + n/(n+1)

一个成功结点的查找长度 = 自身所在层数
一个失败结点的查找长度 = 其父节点所在层数
默认情况下，各种失败情况或成功情况都等概率发生

一共有n个“成功结点”，n+1个“失败结点”。失败结点查找长度为啥是它父节点所在层数？因为它既然失败那肯定是它的父对比发现要么小了要么大了，所以就对比到它父节点，所以对比次数是它父节点所在层数。

当然还有另一种优化的情况，就是在查找概率不相等的时候，把被查概率大的放在靠前的位置可以让我们的ASL更小。

三、折半查找

1.实现

折半折半，顾名思义，就是先对比中间的，看是大了还是小了，然后再在左边/右边分一半，看大了还是小了，一半一半缩小这样。当然，这是基于有序序列的情况。

折半查找，又称“二分查找”，仅适用于有序的顺序表。

比如下面这个顺序表：（从小到大）

7	10	13	16	19	29	32	33	37	41	43
0	1	2	3	4	5	6	7	8	9	10	11	12	13	…（下标）

tableLen = 11

那既然是折半，肯定要知道折一半之后的位置在哪。所以我们用一个 low指针 ，一个 high指针 ，还有一个 mid指针 来辅助， 初始状态下 low = 0（第一个元素），high = tableLen-1（最后一个元素），mid = (low+high)/2

其实这样看的话让mid = (low+high)/2，如果是奇数个还好，比如如果只有3个，low为0，high为2，mid直接就为1，但如果是偶数个，那这个中轴线你有没有发现其实就是往左偏的，也就是左边就比右边少一个（因为(low+high)/2也就相当于向下取整，舍掉余数嘛，如果让它向上取整那就是右边少一个了）。

举两个栗子：

①我们要查找“33”

初始状态下 low = 0（第一个元素），high = tableLen-1也就是10，那么我们mid（ (low+high)/2=5）就是指向 下标5 在的这个元素，也就是“19”，我们发现要找的“33”比“19”大，所以在mid右半边查找，让 low = mid + 1 （6），mid = (low+high)/2（6+10=16, 16/2=8），再接着对比；

所以现在 low 是 6，mid 是 8，下标为8的元素是“37”，我们发现要找的“33”比“37”小，所以在mid左半边找，让 high = mid - 1 （7），mid = (low+high)/2（6+7=13, 13/2=6），再接着对比；

也就是说，现在 high 是 7，mid 是 6（指向和low一样），下标为6的元素是“32”，我们发现要找的“33”比“32”大，所以在mid右半边查找，让 low = mid + 1 （7），mid = (low+high)/2（7+7=14, 14/2=7），再接着对比；

此时！！！皇天不负苦心人，现在 low 是 7，mid 是 7，下标为7的元素是“33”，我们发现要找的“33”和“33”一样，33 == mid，所以查找成功！

②我们要查找“12”

初始状态下 low = 0（第一个元素），high = tableLen-1也就是10，那么我们mid（ (low+high)/2=5）就是指向 下标5 在的这个元素，也就是“19”，我们发现要找的“12”比“19”小，所以在mid左半边查找，让 high = mid - 1 （4），mid = (low+high)/2（0+4=4, 4/2=2），再接着对比；

所以现在 low 是 0，mid 是 2，下标为2的元素是“13”，我们发现要找的“12”比“13”小，所以在mid左半边找，让 high = mid - 1 （1），mid = (low+high)/2（0+1=1, 1/2=0），再接着对比；

也就是说，现在 high 是 1，mid 是 0（指向和low一样），下标为0的元素是“7”，我们发现要找的“12”比“7”大，所以在mid右半边查找，让 low = mid + 1 （1），mid = (low+high)/2（1+1=2, 2/2=1），再接着对比；

此时，现在 low 是 1，mid 是 1，high 也是 1 ，下标为1的元素是“10”，我们发现要找的“12”比“10”大，所以在mid右半边查找，让 low = mid + 1 （2），mid = (low+high)/2（2+1=3, 3/2=1），此时！！！你有没有发现，low>high，这是不应该的，所以查找失败，可以确定这个表里没有“12”。

这俩栗子差不多了。

上述过程用代码其实很简单，就几句：

typedef struct{     //查找表的数据结构（顺序表）int *elem;      //动态数组基址int tableLen;   //表的长度
}SSTable;//折半查找
int binary_search(SSTable L,int key){int low = 0, high = L.tableLen - 1, mid;while(low <= high){mid = (low + high) / 2;     //取中间位置if(L.elem[mid] == key){return mid;         //查找成功则返回所在位置}else if(L.elem[mid] > key){high = mid - 1;     //从前半部分继续查找}else{low = mid + 1;      //从后半部分继续查找}}return -1;                  //查找失败，返回-1
}

还记得我们开头说的，只用于顺序表吗？为啥不用于链表，因为顺序表拥有随机访问的特性，链表没有（链表找中间啥的比较麻烦）。

2.查找判定树

什么是查找判定树？

听起来很高级其实没啥，就是把每次的mid找出来当做根节点。首先mid在中间，mid左边就是左子树元素，mid右边就是右子树元素；mid左边的元素再让左边元素的mid当根节点，再分左右，mid右边的元素再让右边元素的mid当根节点，再分左右……这样就可以构造一棵查找判定树了。

比如上面那个有序表的查找判定树就是这样的：

ASL_成功=（1 * 1 + 2 * 2 + 3 * 4 + 4 * 4 ）/11 = 3
ASL_失败=（3 * 4 + 4 * 8 ）/12 = 11/3

怎么构造一棵查找判定树？

我们在构造查找判定树的时候：

• 如果当前low和high之间有奇数个元素，则mid分割后，左右两部分元素个数相同；
• 如果当前low和high之间有偶数个元素，则mid分割后，左半部分比有半部分少一个元素；

所以折半查找的查找判定树中，若 mid = ⌊（low+high）/2⌋，则对于任何一个结点，必有右子树结点数-左子树结点数=0或1

折半查找的判定树一定是平衡二叉树

因为符合平衡二叉树性质嘛。

那么如果 mid = ⌊（low+high）/2⌋，则含1个元素的查找判定树，含2各元素的查找判定树……含16个元素的查找判定树是什么样的呢（我们不考虑失败结点）？其实按照上面的方法构造就vans了，就是这样：

要注意的就是右子树结点数-左子树结点数=0或1，严格遵循这个我们构造的就没毛病了~

折半查找的判定树中，只有最下面一层是不满的。因此，元素个数为 n 时，树高 h=⌈log₂（n+1）⌉（和完全二叉树计算方法一样的）

还记得我们上面的那个查找判定树吗：

判定树结点关键字：左<中<右，满足二叉排序树的定义；失败结点：n+1 个（等于成功结点的空链域数量）

树高 h = ⌈log₂（n+1）⌉（该树高不包含失败结点）

查找成功的ASL≤h，查找失败的ASL≤h

折半查找的时间复杂度为O(log₂n)

但是！！！不要以为，折半查找的时间复杂度是O(log₂n)，顺序查找的时间复杂度为O(n)，折半查找的速度就一定比顺序查找更快了，这显然不能说那么死，比如你要找的那个数在第一个，我顺序查找直接第一个对比就对比上了，你折半查找还要从中间一个一个过去，所以这要看情况。

小拓展：如果mid = ⌈（low+high）/2⌉，那么判定树是什么样？其实就左右反过来：

• 如果当前low和high之间有奇数个元素，则mid分割后，左右两部分元素个数相同；
• 如果当前low和high之间有偶数个元素，则mid分割后，左半部分比有半部分多一个元素；

如果偶数个那就左比右多了；对于任何一个结点，也变成了左子树结点数-右子树结点数=0或1了。

四、分块查找

1.算法思想

分块查找，人如其名，就是分成一块一块的，先找在哪个块，然后再在块内查找。如下图：

特点：块内无序，块间有序

找在哪个块的时候可以按照顺序查找，也可以按照折半查找（因为块间有序嘛）；找块内元素的时候，只能按照顺序查找（因为块内无序）。

存放每一个块的叫“索引表”，所谓索引表，里面放的就是每一个块的最大关键字；但是我们分块肯定得知道这个快从哪到哪，所以还要存放分块的存储区间，也就是从哪到哪的数组下标。

所以分块查找的结构就显而易见，块，和索引：

//索引表
typedef struct{int maxValue;int low,high;
}Index;//顺序表存储实际元素
int List[100];

分块查找举个栗子，比如想查找“22”，那么先找块，一个一个找发现“30”比“22”大，所以在“30”指向的这个块中找；“30”指向的块的数组下标是6到8，所以在数组下标为6，7，8里顺序查找，找到“22”了，查找成功。

再比如想查找“29”，还是先找块，一个一个找发现“30”比“22”大，所以在“30”指向的这个块中找；“30”指向的块的数组下标是6到8，所以在数组下标为6，7，8里顺序查找，在这个块中没找到“29”，超出分块范围，查找失败。

分块查找，又称索引顺序查找，算法过程如下：

• 在索引表中确定待查记录所属的分块（可顺序，可折半）
• 在块内顺序查找

比如我们用折半查找来查找索引表，我们要查找“30”这个元素，那么我们low=0,high=4,mid=2，一下就找到了“30”，然后就可以直接去“30”指向的这个块中找；“30”指向的块的数组下标是6到8，所以在数组下标为6，7，8里顺序查找，找到“30”了，查找成功

如果我们要查找“19”，那么初始low=0,high=4,mid=2，发现19<30，high=mid-1=1，mid=(low+high)/2=(0+1)/2=0，和low指向一样，发现19>10，low=mid+1=1，mid=(low+high)/2=(1+1)/2=1，此时low，high，mid全指向一样；19<20，high=mid-1=0，mid=(low+high)/2=(1+0)/2=0，此时low>high

若索引表中不包含目标关键字，则折半查找索引表最终停在low>high，要在low所指分块中查找

我们在“20”这个块中找；“20”指向的块的数组下标是2到5，所以在数组下标为2，3，4，5里顺序查找，找到“19”了，查找成功

为什么要在low所指分块中查找呢？因为最终low左边一定小于目标关键字，high右边一定大于目标关键字，而分块存储的索引表中保存的是各个分块的最大关键字，所以要在low所指分块中查找。这官方说的看不懂一点是吧，别急

什么意思呢？你看在我们的low>high之前，是不是得有个low=high，这个时候我们的low要大于high了，要么是现在的这个位置的值小于关键字，要么是现在这个位置的值大于关键字是不，如果小于关键字的话，那就得让low=mid+1，所以才会导致low>high，又因为high所指的小于关键字，所以要在low所指的分块中查找；如果大于关键字的话，那就得让high=mid-1，所以才会导致low>high，又因为low所指的本来就大于关键字，分块的块中存放的是那个块最大的，所以要在low所指的分块中查找。（因为我们存放的分块的块是块中最大的，所以就算在索引表中找不到，那我们最终目的一定是找到比关键字大的那个中最小的那个，这个关键字要是有的话一定是在这个里面，当然这都是我自己的理解，仅供参考。）

图在上面有点远了，拉下来方便看：

再举个栗子，如果我们要查找“54”，继续折半查找……（此处过程省略），最后我们会发现，high=4，low=5（越界了），此时我们也不用继续找什么了，因为low超出索引表查找范围，查找失败

这和上面的也一样，上面说最终停在low>high，要在low所指分块中查找，low指向的都越界了，所以一定是找不到了。

2.查找效率分析（ASL）

讲完了算法思想，现在我们开始分析它的查找效率

我们看上面那个图，一共有14个元素，它们各自被查找的概率都为1/14

若索引表采用顺序查找，则7需要对比2次（一次找块的找到“10”对比1次，一次在块内找的找到“7”对比1次）、10需要对比3次（一次找块的找到“10”对比1次，一次在块内找的找到“10”对比2次）……

若索引表采用折半查找，则30需要对比4次（一次找块的找到“30”对比1次，一次在块内找的找到“30”对比3次）、10需要对比3次（一次找块的找到“10”对比2次<第一次是mid=2,和“30”对比，发下10<30，high=mid-1=1,mid=(low+high)/2=(0+1)/2=0，再和“10”对比一次>，一次在块内找的找到“10”对比2次）……

平均查找长度就是顺序表中每个元素的查找需要对比次数相加求平均。

假设，长度为n的查找表被均匀地分为b块，每块s个元素，如下图所示：

设索引查找和快内查找的平均查找长度分别为 L_I， L_s，则分块查找的平均查找长度为ASL = L_I + L_s

用顺序查找索引表，则 L_I = （1+2+……+b）/ b = （b+1）/2， L_s = （1+2+……+s）/ s = （s+1）/2，则 ASL = （b+1）/2 + （s+1）/2 = （s² + 2s + n）/2s

当s=√n 时，ASL_最小 = √n+1

因为一共有n个元素，被分为b块，每块s个，所以有n=bs，b=n/s，故（b+1）/2 + （s+1）/2 = （ n/s +1）/2 + （s+1）/2 = （s² + 2s + n）/2s = 1/2 * s + 1 + n/2s ，求导得 ASL` = 1/2 - n/(2s²)，当s=√n时导数为0，此时ASL_最小 = √n+1。

也就是说，当我们的顺序表被分为 √n 块，每块有√n 个元素时，查找效率最高。比如如果n = 10000，那么应该分100块，每块100个元素，此时ASL_最小 = 101，这比顺序查找好很多，顺序查找的话ASL就是5000，效率很低。

用折半查找索引表，则 L_I = ⌈log₂（b+1）⌉， L_s = （1+2+……+s）/ s = （s+1）/2，则 ASL = ⌈log₂（b+1）⌉ + （s+1）/2。

查找失败的情况更加复杂，一般不考。

但是我们的查找表是顺序查找表，所以对于增删操作，就会非常不方便，增删一位后面的就都要移动。所以如果对于增删有很大要求，那么就可以将查找表设为动态查找表，也就是用链式存储（如下图所示）：

所以我们得机灵点，随机应变。

---

总结

顺序查找没什么，折半查找要注意low和high是怎么变化的，不要搞错搞漏了；还有就是要注意分块查找的时候，对索引表进行折半查找时，如果索引表中不包含目标关键字，则折半查找最终停在low>high，要在low所指的分块中查找。