408数据结构-折半查找，分块查找 自学知识点整理
前置知识：查找的基本概念
折半查找
折半查找 又称 二分查找 ，它仅适用于有序的顺序表。
因个人习惯，下文均用二分代替折半。
二分查找的基本思想：
- 首先将给定值 k e y key key与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置；
- 若不等，则所需查找的元素只能在中间元素以外的前半部分或者后半部分，然后在缩小的范围内继续进行同样的查找；
例如，在查找表升序排列时，若 k e y key key大于中间元素，则所查找的元素只可能在后半部分。
重复上述步骤，直到查找成功。或者确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。
当二分查找算法选取中间结点时，既可以采用向下取整，又可以采用向上取整。但每次查找的取整方式必须相同。
算法实现如下：
inline int Search_Seq(SSTable L, ElemType key) {//升序排列
int l = 1, r = L.TableLen, mid;//l为left，r为right
while (l <= r) {
mid = (l + r) / 2;//取中间位置
if (L.elem[mid] == key)return mid;//查找成功则返回所在位置
else if (L.elem[mid] > key)r = mid - 1;//从前半部分继续查找
else l = mid + 1;//从后半部分继续查找
}
return -1;//查找失败，返回-1
}
完整代码可看我的Github：传送门
（补充了降序排列的写法，实际上很简单，把从前半部分继续和后半部分继续对调一下即可）
(图片来自王道考研408数据结构2025)
二分查找的过程可用上图所示的二叉树来描述，称为 判定树 。树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值；树中最下面的叶结点都是方形的，它表示查找失败的区间。
从判定树可以看出，查找成功时的查找长度为从根节点到目的结点的路径上的结点数，而查找失败时的查找长度为从根节点到对应失败结点的父结点的路径上的结点数；每个结点值均大于其左子结点值，且均小于其右子节点值。
二分查找的判定树中，若
m
i
d
=
⌊
(
l
+
r
)
/
2
⌋
mid=\left \lfloor \left ( l+r \right ) /2 \right \rfloor
mid=⌊(l+r)/2⌋，则对于任何一个结点，必有右子树结点数-左子树结点数=0或1；若采用向上取整，则反之。
（下图来自王道考研408数据结构课程视频的截图 - 折半查找）
若有序序列有
n
n
n个元素，则对应的判定树有
n
n
n个圆形的非叶结点和
n
+
1
n+1
n+1个方形的叶结点。因此，判定树是一棵平衡二叉树。（后续博客会写）
分析可知，用二分查找法找到给定值的比较次数最多不会超过判定树的高度。在等概率查找时，查找成功的平均查找长度为：
A
S
L
=
1
n
∑
i
=
1
n
l
i
=
1
n
(
1
×
1
+
2
×
2
+
⋯
+
h
×
2
h
−
1
)
=
n
+
1
n
log
2
(
n
+
1
)
−
1
≈
log
2
(
n
+
1
)
−
1
ASL=\frac{1}{n} \sum_{i=1}^{n}l_i=\frac{1}{n} \left ( 1\times 1+ 2\times 2+\cdots + h\times 2^{h-1} \right )=\frac{n+1}{n}\log_{2}{\left ( n+1 \right ) }-1 \approx \log_{2}{\left ( n+1 \right ) }-1
ASL=n1i=1∑nli=n1(1×1+2×2+⋯+h×2h−1)=nn+1log2(n+1)−1≈log2(n+1)−1
式中，
h
h
h是树的高度，并且元素个数为
n
n
n时树高
h
=
⌈
log
2
(
n
+
1
)
⌉
h=\left \lceil \log_{2}{\left ( n+1 \right ) } \right \rceil
h=⌈log2(n+1)⌉。所以，二分查找的时间复杂度为
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)，平均情况比顺序查找的效率高。
知识点回顾：完全二叉树
在图 7.2 7.2 7.2所示的判定树中，等概率的情况下，查找成功（圆形结点）的 A S L = ( 1 × 1 + 2 × 2 + 3 × 4 + 4 × 4 ) / 11 = 3 ASL=(1×1+2×2+3×4+4×4)/11=3 ASL=(1×1+2×2+3×4+4×4)/11=3，查找失败（方形结点）的 A S L = ( 3 × 4 + 4 × 8 ) / 12 = 11 / 3 ASL=(3×4+4×8)/12=11/3 ASL=(3×4+4×8)/12=11/3。
因为二分查找法需要方便地定位查找区域，所以它要求线性表必须具有随机存取的特性。因此，该查找法仅适合于顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列。
分块查找
分块查找 又称 索引顺序查找 ，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。
typedef struct {
ElemType maxValue;
int left, right;
}Index;//索引表
ElemType List[114];//顺序表存储实际元素
分块查找的基本思想：将查找表分为若干子块。块内的元素可以无序，但块间的元素是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的存储区间，索引表按关键字有序排列。（块内无序，块间有序）
分块查找的过程分为两步：第一步是在索引表中确定待查记录所在的块，可以顺序查找或二分查找索引表；第二步是在块内顺序查找。
特别的，若索引表中不包含目标关键字，则二分查找索引表最终会停在
l
e
f
t
>
r
i
g
h
t
left>right
left>right，此时必须在
l
e
f
t
left
left所指的分块中查找。因为在
l
e
f
t
>
r
i
g
h
t
left>right
left>right的上一步，根据二分查找的步骤，一定是
l
e
f
t
=
=
r
i
g
h
t
left==right
left==right的情况，此时同样
m
i
d
=
=
l
e
f
t
mid==left
mid==left，会有两种情况：
- m i d < k e y mid<key mid<key：此情况 l e f t left left后移一位，此时 l e f t left left所指的这个元素一定比 m i d mid mid所指的元素更大。
- m i d > k e y mid>key mid>key：此情况 r i g h t right right前移一位，此时 l e f t left left指向位置不变，所指的这个元素也一定比目标关键字更大。
因此二分查找索引表最终停在
l
e
f
t
>
r
i
g
h
t
left>right
left>right时，必须在
l
e
f
t
left
left所指的分块中查找。
若
l
e
f
t
left
left此时超出索引表范围，则查找失败。
分块查找的平均查找长度为索引查找和块内查找的平均长度之和。设索引查找和块内查找的平均查找长度分别为
L
I
L_I
LI和
L
S
L_S
LS，则分块查找的平均查找长度为：
A
L
S
=
L
I
+
L
S
ALS=L_I+L_S
ALS=LI+LS
将长度为
n
n
n的查找表均匀地分为
b
b
b块，每块有
s
s
s个记录（
n
=
b
s
n=bs
n=bs），在等概率情况下，若在块内和索引表中均采用顺序查找，则平均查找长度为：
A
L
S
=
L
I
+
L
S
=
b
+
1
2
+
s
+
1
2
=
s
2
+
2
s
+
n
2
s
ALS=L_I+L_S=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s}
ALS=LI+LS=2b+1+2s+1=2ss2+2s+n
此时，若
s
=
n
s=\sqrt{n}
s=n，则平均查找长度取最小值
n
+
1
\sqrt{n}+1
n+1。
（下图来自王道考研408数据结构课程视频的截图 - 分块查找）
当需要在块内插入新元素，或者删除元素时，可以采用链式存储结构。
虽然索引表占用了额外的存储空间，索引查找也增加了一定的系统开销，但由于其分块结构，使得在块内查找时的范围较小，因此与顺序查找相比，分块查找的总体效率提升了不少。
二分查找在大题小题中都容易考察，需要重点掌握。分块查找主要在选择题中考察，因此重点掌握其算法思想即可（不会考太复杂的分块平均查找长度计算）。
以上。