【数据结构与算法】第25篇：静态查找（一）：顺序查找与折半查找

一、顺序查找

1.1 基本思想

从头到尾逐个比较，直到找到目标或遍历完整个表。适用于任何线性表，不要求有序。

1.2 哨兵优化

在数组末尾设置一个“哨兵”值为目标值，这样循环中不需要判断是否越界，只需要比较是否相等。

普通版本：每次循环需要检查是否越界

c

int search(int *arr, int n, int key) { for (int i = 0; i < n; i++) { if (arr[i] == key) return i; } return -1; }

哨兵版本：减少一次判断

c

int searchWithSentinel(int *arr, int n, int key) { int i = 0; arr[n] = key; // 设置哨兵 while (arr[i] != key) { i++; } return i == n ? -1 : i; }

1.3 代码实现

c

#include <stdio.h> #include <stdlib.h> // 普通顺序查找 int seqSearch(int *arr, int n, int key) { for (int i = 0; i < n; i++) { if (arr[i] == key) return i; } return -1; } // 哨兵优化顺序查找 int seqSearchWithSentinel(int *arr, int n, int key) { int i = 0; arr[n] = key; // 哨兵放在末尾 while (arr[i] != key) { i++; } return i == n ? -1 : i; } int main() { int arr[] = {3, 7, 1, 9, 5, 2, 8}; int n = sizeof(arr) / sizeof(arr[0]); // 需要额外空间放哨兵 int *arrWithSentinel = (int*)malloc((n + 1) * sizeof(int)); for (int i = 0; i < n; i++) { arrWithSentinel[i] = arr[i]; } printf("数组: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); int key = 5; int pos = seqSearch(arr, n, key); printf("顺序查找 %d 的位置: %d\n", key, pos); pos = seqSearchWithSentinel(arrWithSentinel, n, key); printf("哨兵优化查找 %d 的位置: %d\n", key, pos); key = 10; pos = seqSearchWithSentinel(arrWithSentinel, n, key); printf("哨兵优化查找 %d 的结果: %d\n", key, pos); free(arrWithSentinel); return 0; }

运行结果：

text

数组: 3 7 1 9 5 2 8 顺序查找 5 的位置: 4 哨兵优化查找 5 的位置: 4 哨兵优化查找 10 的结果: -1

二、折半查找（二分查找）

2.1 基本思想

折半查找要求数据有序（通常升序）。每次取中间元素与目标比较：

• 相等 → 找到

• 目标小于中间 → 在左半部分继续查找

• 目标大于中间 → 在右半部分继续查找

2.2 非递归实现

c

int binarySearch(int *arr, int n, int key) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; // 防止溢出 if (arr[mid] == key) { return mid; } else if (arr[mid] < key) { left = mid + 1; } else { right = mid - 1; } } return -1; }

注意：mid = (left + right) / 2在 left 和 right 很大时可能溢出，用left + (right - left) / 2更安全。

2.3 递归实现

c

int binarySearchRecursive(int *arr, int left, int right, int key) { if (left > right) return -1; int mid = left + (right - left) / 2; if (arr[mid] == key) { return mid; } else if (arr[mid] < key) { return binarySearchRecursive(arr, mid + 1, right, key); } else { return binarySearchRecursive(arr, left, mid - 1, key); } }

三、折半查找的判定树

3.1 判定树的概念

折半查找的过程可以用一棵二叉树来描述，称为判定树。树中每个节点代表一次比较。

以有序数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]为例：

text

6 / \ 3 8 / \ / \ 2 5 7 9 / / \ 1 4 10

3.2 查找成功的比较次数

查找成功的比较次数 = 节点在判定树中的深度（根深度为1）

平均查找长度（ASL）：

text

ASL = (1×1 + 2×2 + 4×3 + 3×4) / 10 = (1+4+12+12)/10 = 29/10 = 2.9

3.3 查找失败的比较次数

查找失败时，比较次数 = 从根到外部节点（空指针）路径上的节点数。

四、完整代码演示

c

#include <stdio.h> #include <stdlib.h> // 顺序查找（哨兵版） int seqSearchWithSentinel(int *arr, int n, int key) { int i = 0; arr[n] = key; while (arr[i] != key) i++; return i == n ? -1 : i; } // 折半查找（非递归） int binarySearch(int *arr, int n, int key) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == key) return mid; else if (arr[mid] < key) left = mid + 1; else right = mid - 1; } return -1; } // 折半查找（递归） int binarySearchRec(int *arr, int left, int right, int key) { if (left > right) return -1; int mid = left + (right - left) / 2; if (arr[mid] == key) return mid; else if (arr[mid] < key) return binarySearchRec(arr, mid + 1, right, key); else return binarySearchRec(arr, left, mid - 1, key); } // 打印判定树（简化版） void printDecisionTree(int *arr, int left, int right, int depth) { if (left > right) { for (int i = 0; i < depth; i++) printf(" "); printf("NULL\n"); return; } int mid = left + (right - left) / 2; for (int i = 0; i < depth; i++) printf(" "); printf("%d\n", arr[mid]); printDecisionTree(arr, left, mid - 1, depth + 1); printDecisionTree(arr, mid + 1, right, depth + 1); } int main() { // 顺序查找测试 int arrSeq[] = {3, 7, 1, 9, 5, 2, 8}; int nSeq = sizeof(arrSeq) / sizeof(arrSeq[0]); int *arrWithSentinel = (int*)malloc((nSeq + 1) * sizeof(int)); for (int i = 0; i < nSeq; i++) arrWithSentinel[i] = arrSeq[i]; printf("=== 顺序查找 ===\n"); printf("数组: "); for (int i = 0; i < nSeq; i++) printf("%d ", arrSeq[i]); printf("\n"); int key = 5; int pos = seqSearchWithSentinel(arrWithSentinel, nSeq, key); printf("查找 %d 的位置: %d\n", key, pos); // 折半查找测试 int arrBin[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int nBin = sizeof(arrBin) / sizeof(arrBin[0]); printf("\n=== 折半查找 ===\n"); printf("有序数组: "); for (int i = 0; i < nBin; i++) printf("%d ", arrBin[i]); printf("\n"); key = 7; pos = binarySearch(arrBin, nBin, key); printf("非递归查找 %d 的位置: %d\n", key, pos); key = 3; pos = binarySearchRec(arrBin, 0, nBin - 1, key); printf("递归查找 %d 的位置: %d\n", key, pos); key = 11; pos = binarySearch(arrBin, nBin, key); printf("查找不存在的 %d 结果: %d\n", key, pos); printf("\n=== 判定树（前3层示意）===\n"); printf("折半查找判定树:\n"); printDecisionTree(arrBin, 0, nBin - 1, 0); free(arrWithSentinel); return 0; }

运行结果：

text

=== 顺序查找 === 数组: 3 7 1 9 5 2 8 查找 5 的位置: 4 === 折半查找 === 有序数组: 1 2 3 4 5 6 7 8 9 10 非递归查找 7 的位置: 6 递归查找 3 的位置: 2 查找不存在的 11 结果: -1 === 判定树（前3层示意）=== 折半查找判定树: 6 3 2 1 NULL NULL NULL 5 4 NULL NULL NULL 8 7 NULL NULL 9 NULL 10 NULL NULL

五、复杂度分析

六、顺序查找 vs 折半查找

七、小结

这一篇我们学习了两种静态查找算法：

折半查找的核心：每次将查找范围缩小一半，时间复杂度O(log n)。

下一篇我们讲插值查找与斐波那契查找。

八、思考题

1. 顺序查找的哨兵优化能提升多少性能？为什么？

2. 折半查找中，为什么用mid = left + (right - left) / 2而不是(left + right) / 2？

3. 对于长度为15的有序数组，折半查找的判定树是什么样的？ASL是多少？

4. 如果数据是有序但频繁插入删除，适合用折半查找吗？为什么？

欢迎在评论区讨论你的答案。