查找：顺序查找、折半查找、分块查找

概念

查找是在一个数据集合中找出满足某条件的元素。平均查找长度（ASL, Average Search Length）是衡量查找算法效率的指标：

$$ASL=\sum _{i=1}^n{P}_i\cdot C_i$$

其中 $P_i$ 是查找第 i 个元素的概率，$C_i$ 是找到它所需的关键字比较次数。等概率（$P_i=1/n$）时 $ASL=\frac{1}{n}\sum C_i$。

一句话理解：ASL 就是"平均要比较多少次"，它是 408 里查找章节唯一的计算题考点。

三种静态查找方法：

方法	要求	平均时间复杂度
顺序查找	无（有序无序都行）	$O(n)$
折半查找	有序 + 顺序存储	$O({\log }_{2}n)$
分块查找	分块之间有序，块内无序	$O(\sqrt{n})$ 量级（最佳配置）

原理

一、顺序查找（Sequential Search）

从表的一端开始逐个比关键字。

哨兵技巧：把待查关键字放在下标 0（a[0] = key），从表尾往前扫，一定能"找到"，于是循环里不必判断下标越界——循环条件从两个（没到头 && 没找到）减为一个。

含哨兵的顺序查找（数组 1..n 存数据，0 号位放 key）：
    a[0] = key;  i = n
    while a[i] != key:  i--
    return i        /* 返回 0 表示查找失败 */

ASL（等概率）：

• 查找成功：第 i 个元素需比较 i 次（1 ≤ i ≤ n），

$$AS{L}_{\mathrm{成}\mathrm{功}}=\frac{1}{n}\sum _{i=1}^{n}i=\frac{n+1}{2}$$

• 查找失败：要跟全部 n 个元素都比一遍，还要再做一次"表已扫完"的判断 → $n+1$ 次。

关于失败次数的口径：王道教材按 $n+1$ 计（含最后一次越界/哨兵判断）；若只数"和元素比过几次"则是 $n$。答题时按教材取 $n+1$，并在图里写清楚。

有序表的顺序查找：成功仍是 $\frac{n+1}{2}$，但失败可以提前终止，共 $n+1$ 个失败区间，比较次数依次为 $1,2,\dots ,n,n$：

$$AS{L}_{\mathrm{失}\mathrm{败}}=\frac{\frac{n(n+1)}{2}+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$$

二、折半查找（Binary Search）

前提是有序且顺序存储（单链表不行，因为要 $O(1)$ 定位中间位置）。

BinarySearch(a, n, key):
    low = 1;  high = n
    while low <= high:
        mid = (low + high) / 2          /* 向下取整 */
        if a[mid] == key: return mid
        else if a[mid] > key: high = mid - 1
        else: low = mid + 1
    return 0                            /* 失败 */

判定树：把每次 mid 作为根、左右子区间作为左右子树画出来，得到一棵二叉排序树形状的决策树。

• 每个内部结点对应一次成功查找，比较次数 = 该结点所在层数；
• 每个空链接补一个方形失败结点（共 $n+1$ 个），比较次数 = 该失败结点上面的那条路径上的内部结点个数；
• 判定树高度 = $\lceil {\log }_2(n+1)\rceil$ = 最大比较次数（也即查找成功的最坏时间复杂度量级）。
• 判定树是平衡二叉树（任意两子树的高度差 ≤ 1），但不是完全二叉树——除非 n 恰好是 $2^k-1$。

为什么 $mid=\lfloor (low+high)/2\rfloor$？向下取整意味着偏向左（较矮）子树：这也解释了为什么判定树右子树往往比左子树高一层。

三、分块查找（索引顺序查找）

把 n 个元素分成 b 块、每块 s 个元素（$b=n/s$），另建一张索引表记每块的最大关键字与块起始地址：

• 块间有序：第 i 块的所有关键字都小于第 i+1 块的最小关键字（于是索引表本身有序，可折半查）；
• 块内无序：块内只能顺序查。

两步走：先在索引表里定位目标块（顺序或折半），再进块内顺序查，故

$$ASL=AS{L}_{\mathrm{查}\mathrm{索}\mathrm{引}}+AS{L}_{\mathrm{块}\mathrm{内}}$$

• 两者都用顺序查找且等概率：$ASL=\frac{b+1}{2}+\frac{s+1}{2}$，由 $s=n/b$ 得最小化条件 $b=s=\sqrt{n}$，此时 $AS{L}_{min}=\sqrt{n}+1$；
• 索引表用折半查找（$b$ 较小时收益有限）：$ASL=\lceil {\log }_2(b+1)\rceil +\frac{s+1}{2}$。

三者对比

	顺序查找	折半查找	分块查找
表的要求	无	有序 + 顺序存储	块间有序
成功 ASL	$\frac{n+1}{2}$	$\approx {\log }_2(n+1)-1$	$\frac{b+1}{2}+\frac{s+1}{2}$
失败 ASL	$n+1$	见判定树	索引 + 末块扫 tail
时间复杂度	$O(n)$	$O({\log }_{2}n)$	$O(\sqrt{n})$ 配置最优
存储结构	顺序/链式均可	只能顺序	顺序 + 索引表
插入删除	$O(1)$（链式）	$O(n)$（要移动）	块内移动有限

示例

有序表 $a=[1,2,3,4,5,6,7,8,9,10,11,12]$，$n=12$，等概率查找。分别求三种查找的成功 / 失败 ASL。

1. 顺序查找

$$AS{L}_{\mathrm{成}\mathrm{功}}=\frac{n+1}{2}=\frac{13}{2}=6.5$$$$AS{L}_{\mathrm{失}\mathrm{败}}=n+1=13(\text{若只数与元素的比较，则为 }12)$$

2. 折半查找：画判定树

mid = ⌊(low + high)/2⌋，n = 12：

                            ⑥                          第 1 层：1 个
                     ┌──────┴──────┐
                     ③              ⑨                  第 2 层：2 个
                ┌────┴────┐   ┌─────┴─────┐
                ①          ④  ⑦           ⑪           第 3 层：4 个
                 └ ②        └ ⑤  └ ⑧     ┌┴┐
                                         ⑩  ⑫         第 4 层：5 个

   节点总数 = 1 + 2 + 4 + 5 = 12 = n   ✓
   失败结点 = 12 + 1 = 13 个（图中每个空链接处补一个方形结点）

关键 ASL 计算：

$$AS{L}_{\mathrm{成}\mathrm{功}}=\frac{1\times 1+2\times 2+4\times 3+5\times 4}{12}=\frac{1+4+12+20}{12}=\frac{37}{12}\approx 3.08$$

失败结点：挂在路径末端的内部结点下。数一数：

失败位置	个数	比较次数
内部结点 ①、④、⑦ 的空左子树（区间 $(-\mathrm{\infty },1)$、$(3,4)$、$(6,7)$）	3	3
内部结点 ②、⑤、⑧、⑩、⑫ 的两侧空子树	10	4

$$AS{L}_{\mathrm{失}\mathrm{败}}=\frac{3\times 3+10\times 4}{13}=\frac{9+40}{13}=\frac{49}{13}\approx 3.77$$

最大比较次数 = 判定树高 = $\lceil {\log }_2(13)\rceil =4$。

对比一目了然：n = 12 时折半查找平均 3.08 次，顺序查找要 6.5 次；n 越大差距越悬殊。

3. 分块查找：n = 100，b = 10 块，每块 s = 10 个

索引查找方式	计算式	ASL
顺序查索引	$\frac{10+1}{2}+\frac{10+1}{2}=5.5+5.5$	11.0
折半查索引	$\lceil {\log }_{2}11\rceil +5.5=4+5.5$	9.5
最优块大小	$s=\sqrt{100}=10$	$AS{L}_{min}=\sqrt{n}+1=11$

横向对比：同样 100 个元素，顺序查找平均要 50.5 次，分块查找只要 11 次——分块的价值就在于此。若整表有序用折半查找则只要 $\approx 6$ 次，但代价是必须维持全局有序、插入代价高。

C 语言：三种查找 + 哨兵写法

#include <stdio.h>

#define MAXN 100

/* 顺序查找（哨兵版）：a[1..n] 存数据，a[0] 放哨兵 */
int seqSearch(int a[], int n, int key) {
    a[0] = key;                       /* 哨兵 */
    int i = n;
    while (a[i] != key) i--;          /* 因有哨兵，不必判断 i > 0 */
    return i;                         /* 0 表示查找失败 */
}

/* 折半查找：表必须有序且顺序存储 */
int binSearch(int a[], int n, int key) {
    int low = 1, high = n;
    while (low <= high) {
        int mid = (low + high) / 2;   /* 向下取整 */
        if (a[mid] == key) return mid;
        else if (a[mid] > key) high = mid - 1;
        else low = mid + 1;
    }
    return 0;
}

/* 递归版折半查找 */
int binSearchRec(int a[], int low, int high, int key) {
    if (low > high) return 0;
    int mid = (low + high) / 2;
    if (a[mid] == key) return mid;
    if (a[mid] > key) return binSearchRec(a, low, mid - 1, key);
    return binSearchRec(a, mid + 1, high, key);
}

/* 分块查找：idx[] 为每块最大关键字，st[]/ed[] 为块的起止下标，1-based */
typedef struct { int maxKey; int st, ed; } Block;
int blockSearch(int a[], Block idx[], int b, int key) {
    int bi = -1;
    for (int i = 0; i < b; i++)          /* 顺序查索引 */
        if (key <= idx[i].maxKey) { bi = i; break; }
    if (bi < 0) return 0;
    for (int i = idx[bi].st; i <= idx[bi].ed; i++)   /* 块内顺序查 */
        if (a[i] == key) return i;
    return 0;
}

int main(void) {
    int a[MAXN];
    int n = 12;
    for (int i = 1; i <= n; i++) a[i] = i;

    printf("seqSearch(7)  = %d\n", seqSearch(a, n, 7));    /* 7  */
    printf("seqSearch(99) = %d\n", seqSearch(a, n, 99));   /* 0  失败 */
    printf("binSearch(9)  = %d\n", binSearch(a, n, 9));    /* 9  */
    printf("binSearch(99) = %d\n", binSearch(a, n, 99));   /* 0  失败 */
    printf("binSearchRec(2) = %d\n", binSearchRec(a, 1, n, 2)); /* 2 */

    /* 分块：10 个数分 3 块 */
    int t[MAXN] = {0, 8, 3, 17, 5, 12, 25, 20, 30, 28};
    int tn = 9;
    Block idx[3] = { {8,1,3}, {17,4,6}, {30,7,9} };   /* 块间递增：8 < 17 < 30 */
    printf("blockSearch(12) = %d\n", blockSearch(t, idx, 3, 12));  /* 5 */
    printf("blockSearch(99) = %d\n", blockSearch(t, idx, 3, 99));  /* 0 */
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

Python 对照

a = list(range(1, 13))          # 下标 0..11 对应元素 1..12
n = len(a)

def bs_count(arr, key):
    """返回 (比较次数, 是否找到)"""
    lo, hi, cnt = 0, len(arr) - 1, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        cnt += 1
        if arr[mid] == key: return cnt, True
        if arr[mid] > key: hi = mid - 1
        else: lo = mid + 1
    return cnt, False

# 成功 ASL
success = [bs_count(a, k)[0] for k in a]
print("成功比较次数:", success)
print("成功 ASL = %d/%d = %.4f" % (sum(success), n, sum(success) / n))      # 37/12 = 3.0833

# 失败 ASL：n+1 个失败区间，各取一个代表值
fail_keys = [0.5] + [i + 0.5 for i in range(1, n)] + [n + 0.5]
fail = [bs_count(a, k)[0] for k in fail_keys]
print("失败区间数:", len(fail), " 比较次数:", fail)
print("失败 ASL = %d/%d = %.4f" % (sum(fail), len(fail), sum(fail) / len(fail)))  # 49/13 = 3.7692

import math
print("判定树高 = ceil(log2(13)) =", math.ceil(math.log2(n + 1)))           # 4

# 顺序查找 ASL
print("\n顺序查找 成功 ASL = %.2f, 失败 ASL(含越界判断) = %d" % ((n + 1) / 2, n + 1))
print("有序表顺序查找 失败 ASL = n/2 + n/(n+1) = %.4f" % (n / 2 + n / (n + 1)))
print("顺序查找成功 ASL 理论值 =", (n + 1) / 2)

# 分块查找 ASL
N, b, s = 100, 10, 10
print("\n分块 n=%d: 顺序索引 %.2f, 折半索引 %.2f, 最优(√n+1) %.2f"
      % (N, (b + 1) / 2 + (s + 1) / 2, math.ceil(math.log2(b + 1)) + (s + 1) / 2, math.sqrt(N) + 1))

# 扫一遍不同 block size，确认 √n 附近最小
for s_ in range(2, 51):
    bb = N // s_
    if bb * s_ != N: continue
    val = (bb + 1) / 2 + (s_ + 1) / 2
    if s_ in (5, 10, 20, 25, 50):
        print("  s=%2d b=%2d ASL=%.2f" % (s_, bb, val))

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

考点

1. 必背结论

• $ASL=\sum P_i{C}_i$，等概率时 $=\frac{1}{n}\sum C_i$。
• 顺序查找：成功 $\frac{n+1}{2}$，失败 $n+1$（教材口径）；哨兵把循环里的两个判断减为一个。
• 折半查找：判定树高度 $=\lceil {\log }_2(n+1)\rceil$ = 最大比较次数；$n$ 个元素恰有 $n+1$ 个失败结点。
• 折半查找要求有序 + 顺序存储，单链表不能做折半查找。
• 分块查找：块间有序、块内无序；最佳 $b=s=\sqrt{n}$，$AS{L}_{min}=\sqrt{n}+1$。
• $mid$ 向下取整时，较矮的子树偏左，判定树整体略向右倾斜；换用向上取整会得到镜像形状的判定树，ASL 可能不同。

2. 解题套路

• 求折半查找 ASL：先画判定树（$mid$ 取整方式要与题目一致），数各层结点个数，按"层数 × 个数"加权求和。
• 求失败 ASL：不要忘了失败结点数是 $n+1$；它们的比较次数 = 路径上内部结点个数。
• 黑盒判断题："某元素在折半查找中最多比较几次" → 查判定树高 $\lceil {\log }_2(n+1)\rceil$。
• 分块查找题：先分清"索引用什么查、块内用什么查"，再套两段相加的公式。

3. 易错点

• 最好养成习惯：判定树内部结点数 = n，失败结点数 = n + 1，别写反。
• 认为折半查找一定比顺序查找快。当 n 很小时（比如 n ≤ 3）顺序查找可能更快，而且折半需要表有序，维护有序本身有代价。
• 忘了折半查找要求顺序存储：链表上即使有序也无法 $O(1)$ 定位 mid。
• mid 的取整方式（⌊(low+high)/2⌋ vs ⌈(low+high)/2⌉）会改变判定树形状与 ASL。默认按向下取整。
• 计算失败 ASL 时把比较次数记成失败结点所在的层数（多算了 1）。正确是"路径上内部结点的个数"。
• 分块查找里的 $AS{L}_{min}=\sqrt{n}+1$ 只适用于索引与块内都用顺序查找；若索引用折半查找，最小值不再是 $\sqrt{n}+1$。
• 混淆"有序表的顺序查找"与"折半查找"的失败 ASL：前者 $\frac{n}{2}+\frac{n}{n+1}$，后者要看判定树，两者不是一回事。

小结

• ASL 是查找算法唯一的量化指标；$C_i$ 一律按关键字比较次数计。
• 顺序查找 $O(n)$（成功 $\frac{n+1}{2}$），折半查找 $O({\log }_{2}n)$（画判定树算 ASL），分块查找在 $\sqrt{n}$ 量级。
• 折半必须有序 + 顺序存储；分块只要求块间有序，是折中方案。
• 下一步：以上都限定在内存里的顺序表/数组上，数据量一大要落到磁盘上，就轮到 B 树与 B+ 树出场了。

下一篇：B 树与 B+ 树