【数据结构】考研数据结构重点精讲：折半查找核心思想与判定树深度解析

蒙奇D索隆

发布于 2025-10-17 08:24:35

4920

文章被收录于专栏：蒙奇D索隆的学习笔记蒙奇D索隆的学习笔记

(折半查找)

导读

大家好，很高兴又和大家见面啦！！！

在上一篇内容中，我们掌握了查找算法的基础——顺序查找。

其核心定义是：从线性表的一端开始，依次将每个元素的关键字与给定值 key 进行比较，直到找到目标或遍历完整个表。

该博客重点探讨了顺序查找的两个关键层面：

基本优化思想：引入了“哨兵” 机制，通过在表头预留位置来避免每次循环中的越界检查，从而优化了代码效率。
在有序数组中的应用：特别分析了当线性表有序时，顺序查找在查找失败的情况下可以提前终止（当遇到第一个大于 key 的元素时即可确认失败），但其平均查找长度（ASL）在成功情况下仍为 (n+1)/2，时间复杂度 O(n) 的效率瓶颈并未改变。

这表明，顺序查找的实现简单且通用，但其线性扫描的特性限制了其在大量数据中的查找效率。那么，是否存在一种算法，能够真正利用“数据有序”这一条件，实现效率的飞跃？

答案是肯定的，这正是本篇博客要深入解析的折半查找（二分查找）。它是一种专为有序顺序表设计的高效算法，其核心思想是“跳跃式”的二分比较，而非“步进式”的线性扫描。

阅读本篇博客，您将清晰地看到效率是如何从线性 O(n) 提升到对数级 O(log n) 的。我们将深入探讨：

算法核心：如何通过 low, mid, high 三个指针动态划分“比较区”、“小值区”和“大值区”，实现快速范围缩小。
完整示例：通过有序表 {7, 10, 13, 16, 19, 29, 32, 33, 37, 41, 43}，一步步演示查找过程。
性能证明：通过判定树模型量化分析其性能，对比顺序查找，直观展示其巨大优势。

如果您对顺序查找的原理、优化及其局限已有了解，那么本篇关于二分查找的内容，将是您学习如何利用数据有序性实现高效检索的必然进程。

一、折半查找

折半查找，也称为二分查找（Binary Search），是一种在有序数组中快速查找特定元素的算法。它的核心思想是不断将待查找的区间对半分，通过比较中间元素与目标值来缩小搜索范围，从而大幅提高查找效率。

1.1 定义

折半查找是一种基于分治策略的搜索算法，适用于有序的线性表（最常见的是数组）。

1.2 基本思想

折半查找的基本思想如下所示：

首先将给定值 key 与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置
若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分，然后在缩小的范围内继续进行同样的查找。
重复上述步骤，直至找到给定值，或者确定表中没有所需要查找的元素为止

下面我们简单的说明一下：

graph LR
a--->b--->c--->d--->e--->f

在上图这个数组中，有6个元素，具体的元素值，这里我们就不讨论了。在这个数组中，其中间元素为 c ，因此我们会将该值与指定值 key 进行比较，这时会有三种情况：

c == key 则说明我们找到了指定值，直接返回 c 值的存储位置
c < key 则说明 key 值在 c 值的右侧，即 key 值在 d、e、f 这三个值之间
c > key 则说明 key 值在 c 值的左侧，即 key 值在 a、b 这两个值之间

接下来我们按照确定的范围继续重复 key 与范围内的中间值比较即可，直到查找成功，或在数组中找不到该值。

1.3 算法实现

在折半查找中，我们通常会定义三个变量：low/mid/high，这三个变量分别代表着指向数组下标的指针：

low ：数组区间最左侧下标
mid ：数组区间最中间下标
high：数组区间最右侧下标

其中，这三者关系满足：mid = (high - low) / 2 + low ，在不考虑整型溢出的情况时，我们可以表示为：mid = (low + high) / 2 ；

整个算法的实现是通过一个 while 循环完成，如下所示：

int Binary_Search(SSTable l,ElemType key) {
	int low = 0, high = l.Tablelen - 1, mid = 0;
	while (low <= high) {
		mid = (high - low) / 2 + low;
		if (l.elem[mid] == key) {
			return mid;
		}
		else if (l.elem[mid] < key) {
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}
	return -1;
}

在二分查找中，实际上是将数组分成了三个区域：

graph LR
a[low, mid - 1]--->b[mid]--->c[mid + 1, high]

其中，mid 区是来与给定值 key 作比较的，我们可以将其称之为比较区； low, mid - 1 区是当比较结果满足 arr[mid] > key 时，我们选择的区域，我们可以将其称之为小值区； mid + 1, high 区是当比较结果满足 arr[mid] < key 时，我们选择的区域，我们可以将其称之为大值区；

在整个查找的过程中，我们通过比较区的结果来确定给定值 key 最终的位置：

当 key == arr[mid] 时，此时的比较区就是给定值，其下标即为给定值在数组中的下标
当 key < arr[mid] 时，表示此时的比较区的值要比给定值大，那说明给定值应该位于左侧的小值区；
- 当 key 位于小值区时，指针 low 指向的数组下标保持不变，指针 high 需要指向小值区的右侧边缘，即 mid - 1 ，之后我们需要在该区域继续进行查找；
当 key > arr[mid] 时，表示此时的比较区的值要比给定值小，那说明给定值应该位于右侧的大值区；
- 当 key 位于大值区时，指针 high 指向的数组下标保持不变，指针 low 需要指向大值区的左侧边缘，即 mid + 1 ，之后我们需要在该区域继续进行查找；

PS: 这里提到的比较区，小值区与大值区是我个人为了更好的区分，而给其做的命名，如有雷同，纯属巧合。就目前而言，我还没有在其它的课程中听到过这种命名方式，因此大家如果不习惯的话，也可以将其称为左侧，中间和右侧，具体的命名只需要能够帮助大家更好的理解二分查找的原理即可。

下面我们以一个实例来展示一下二分查找的过程；

已知11个元素的有序表 {7, 10, 13, 16, 19, 29, 32, 33, 37, 41, 43} ，要查找的值为 key1 = 11, key2 = 32 ，接下来我们就来展示一下具体的查找过程：

首先，指针 low 指向的是数组的最左侧，即 low = 0，指针 high 指向的是数组的最右侧，即 high = 10

graph TB
a[7<br>0<br>low]
b[10<br>1]
c[13<br>2]
d[16<br>3]
e[19<br>4]
f[29<br>5]
g[32<br>6]
h[33<br>7]
i[37<br>8]
j[41<br>9]
k[43<br>10<br>high]

通过公式 mid = (high - low) / 2 + low 我们可以得到指针 mid 指向的比较区下标为 mid = (10 - 0) / 2 + 0 = 5 ，该区域所指向的元素值为：arr[mid] = 29

graph TB
a[7<br>0<br>low]
b[10<br>1]
c[13<br>2]
d[16<br>3]
e[19<br>4]
f[29<br>5<br>mid]
g[32<br>6]
h[33<br>7]
i[37<br>8]
j[41<br>9]
k[43<br>10<br>high]

接下来我们可以进行第一次比较，通过比较我们可以得到：key1 < arr[mid]，也就是说：key1 落在了小值区，因此我们需要移动指针 high 使其指向小值区的最右侧：high = mid - 1 = 4

graph TB
a[7<br>0<br>low]
b[10<br>1]
c[13<br>2]
d[16<br>3]
e[19<br>4<br>high]

下面我们继续通过公式：mid = (high - low) / 2 + low 我们可以得到指针 mid 指向的比较区下标为 mid = (4 - 0) / 2 + 0 = 2 ，该区域所指向的元素值为：arr[mid] = 13

graph TB
a[7<br>0<br>low]
b[10<br>1]
c[13<br>2<br>mid]
d[16<br>3]
e[19<br>4<br>high]

接下来我们可以进行第二次比较，通过比较我们可以得到：key1 < arr[mid] ，也就是说明：key1 落在了小值区，因此我们需要移动指针 high 使其指向小值区的最右侧：high = mid - 1 = 1

graph TB
a[7<br>0<br>low]
b[10<br>1<br>high]

下面我们继续通过公式：mid = (high - low) / 2 + low 我们可以得到指针 mid 指向的比较区下标为 mid = (1 - 0) / 2 + 0 = 0 ，该区域所指向的元素值为：arr[mid] = 7

graph TB
a[7<br>0<br>low/mid]
b[10<br>1<br>high]

接下来我们可以进行第三次比较，通过比较我们可以得到：key1 > arr[mid] ，也就是说明：key1 落在了大值区，因此我们需要移动指针 low 使其指向大值区的最左侧：low = mid + 1 = 0 + 1 = 1

graph TB
b[10<br>1<br>low/high]

下面我们继续通过公式：mid = (high - low) / 2 + low 我们可以得到指针 mid 指向的比较区下标为 mid = (1 - 1) / 2 + 1 = 1 ，该区域所指向的元素值为：arr[mid] = 10

graph TB
b[10<br>1<br>low/high/mid]

接下来我们可以进行第四次比较，通过比较我们可以得到：key1 > arr[mid] ，也就是说明：key1 落在了大值区，因此我们需要移动指针 low 使其指向大值区的最左侧：low = mid + 1 = 1 + 1 = 2

graph TB
b[10<br>1<br>high]
c[13<br>2<br>low]

此时，指针 low > high 说明我们无法从数组中找到与 key1 值相等的元素，因此我们返回 -1
同理，当我们在表中查找 key2 时，我们只需要3次比较，就可以找到与 key2 相等的元素；

二、折半查找的二叉树表示

如果我们将折半查找的过程用一棵二叉树来表示，则我们可以得到下面这棵二叉树：

graph TB
a((7<br>0))
b((10<br>1))
c((13<br>2))
d((16<br>3))
e((19<br>4))
f((29<br>5))
g((32<br>6))
h((33<br>7))
i((37<br>8))
j((41<br>9))
k((43<br>10))
f--->c
f--->i
c--->a
c--->d
a--->n1[NULL]
a--->b
b--->n5[NULL]
b--->n6[NULL]
d--->n2[NULL]
d--->e
e--->n7[NULL]
e--->n8[NULL]
i--->g
i--->j
g--->n3[NULL]
g--->h
h--->n9[NULL]
h--->n10[NULL]
j--->n4[NULL]
j--->k
k--->n11[NULL]
k--->n12[NULL]

其中，树的根结点就是每轮查找的过程中，指针 mid 指向的元素。像上图这种用来表示二分查找过程的二叉树，我们将其称之为判定树。

树中的每个圆形结点表示一个关键字（记录），结点中的值为该关键字（记录）的值；

树中的叶结点均为矩形结点，表示的是查找失败的区间，如关键字 7 所在结点对应的左子树为 NULL ，该区域表示的是区间 (-\infty, 7) ，即所有小于 7 的值均位于该结点；同理，关键字 10 所在的结点对应的左子树表示的是区间 (7, 10) ，右子树表示的区间是 (10, 13)；

2.1 算法评价

在这棵二叉树中，我们不难发现，在二分查找中，关键字的比较次数与其结点所在的树的层数一致：

第一层结点：关键字比较1次
第二层结点：关键字比较2次
第三层结点：关键字比较3次
第四层结点：关键字比较4次
第五层结点：关键字比较5次

在前面给的例子中，我们可以看到，查找成功时有11个结点，查找失败时，有12个结点，因此其平均查找长度分别为：

$$ \begin{align*} ASL_{成功} & = \sum\limits^{11}{i = 1}P_iC_i \ ASL{成功} & = 1 * 1 * \frac{1}{11} + 2 * 2 * \frac{1}{11} + 4 * 3 * \frac{1}{11} + 4 * 4 * \frac{1}{11} \ ASL_{成功} & = \frac{1 * 1 + 2 * 2 + 4 * 3 + 4 * 4}{11} \ ASL_{成功} & = \frac{1 + 4 + 12 + 16}{11} \ ASL_{成功} & = \frac{33}{11} \ ASL_{成功} & = 3 \ \hline ASL_{失败} & = \sum\limits^{12}{i = 1}P_iC_i \ ASL{失败} & = 4 * 3 * \frac{1}{12} + 8 * 4 * \frac{1}{12} \ ASL_{失败} & = \frac{4 * 3 + 8 * 4}{12} \ ASL_{失败} & = \frac{12 + 32}{12} \ ASL_{失败} & = \frac{44}{12} \ ASL_{失败} & = \frac{11}{3} \ ASL_{失败} & = 3.67 \end{align*} $$

若我们对这组有序数组采用顺序查找，其平均查找长度分别为：

$$ \begin{align*} ASL_{成功} &= \frac{11 + 1}{2} = \frac{12}{2} = 6 \ ASL_{失败} &= 12 \end{align*} $$

从平均查找长度上我们不难看出，不管是成功还是失败，二分查找的平均查找长度远小于顺序查找的平均查找长度；

也就是说明我们在对有序数组进行查找操作时，可以优先考虑二分查找。

结语

今天的内容到这里就全部结束了！！！

通过本篇的详细讲解，我们深入探讨了折半查找（二分查找）这一高效算法。现在，让我们一起来回顾一下核心要点：

核心前提：算法的威力建立在有序性之上，它严格要求数据存储在顺序表中并保持有序，这是其实现效率飞跃的基石。
算法精髓：我们深入剖析了其“分而治之”的思想，通过 low, mid, high 三个指针动态划分比较区、小值区与大值区，将时间复杂度从顺序查找的 O(n) 优化至惊人的 O(log n)。
性能验证：通过引入判定树这一强大的分析工具，我们不仅量化了其性能——成功情况下平均查找长度（ASL）远低于顺序查找，更从数学模型上深刻理解了其高效性的来源。

然而，正如我们所看到的，二分查找的强大伴随着严格的限制：必须有序，且最好为顺序存储。那么，在面对海量数据或需要频繁动态更新的场景时，维护一个完全有序的表可能代价高昂。是否存在一种折中的方案，既能获得比顺序查找更好的性能，又比二分查找更具灵活性呢？

这正是我们下一篇博客要探讨的主题——分块查找。它将揭示如何通过建立“索引表”的方式，在“无序”的海洋中建立“有序”的岛屿，实现一种兼具灵活与效率的查找策略，巧妙地在顺序查找和二分查找之间找到平衡点。

✨ 欢迎互动与交流！