考研笔记

顺序查找与分块查找

这两节放在一起，是因为分块查找就是顺序查找套了一层索引。

顺序查找是本章唯一对存储结构和有序性都不提要求的方法——顺序表、链表、有序、无序，全都能用。代价是 与 同阶。折半查找 反过来：快，但要求必须顺序存储且必须有序。

分块查找是这两者的折中：教材原话是「它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找」。理解它的关键是看清块内和块间的有序性是分开要求的。

机制

一般线性表的顺序查找与哨兵

从表的一端开始逐个比较关键字，走到另一端还没找到就返回失败。教材给的算法从后往前找，并在 ST.elem[0] 放一个哨兵：

typedef struct{
    ElemType *elem;      //动态数组基址
    int TableLen;        //表的长度
}SSTable;
 
int Search_Seq(SSTable ST, ElemType key){
    ST.elem[0] = key;                                  //"哨兵"
    for(int i = ST.TableLen; ST.elem[i] != key; --i);  //从后往前找
    return i;      //查找成功返回下标；查找失败返回 0
}

哨兵的作用不是加速比较，是取消边界判断。 循环条件里本来要写 i >= 1 && ST.elem[i] != key，放了哨兵之后 i 一定会在某处停下——找到了停在目标，没找到停在 0。返回 0 就是查找失败，这一点正好被数组下标从 1 开始使用的约定接住了。

定位第 个元素需要比较 次（从后往前数），于是

成功不成功

若各元素查找概率不等，应把记录按查找概率从大到小重排——查得多的放前面（教材的措辞是「按查找概率由小至大重新排列」，因为它的算法是从后往前扫）。

有序线性表的顺序查找：只有失败变快了

若事先知道表按关键字有序，查找失败时不必比到表的另一端：扫到第 个元素发现它已经不小于 key，就可以断定不存在，直接返回失败。

用判定树描述：圆形结点表示表中存在的元素，矩形结点称为失败结点。有 个圆形结点就相应地有 个失败结点。

flowchart TD
    A(("10")) --- F1["(−∞,10)"]
    A --- B(("20"))
    B --- F2["(10,20)"]
    B --- C(("30"))
    C --- F3["(20,30)"]
    C --- D(("40"))
    D --- F4["(30,40)"]
    D --- E(("50"))
    E --- F5["(40,50)"]
    E --- G(("60"))
    G --- F6["(50,60)"]
    G --- F7["(60,+∞)"]

    classDef ok fill:#e3f2fd,stroke:#1565c0
    classDef fail fill:#ffe0b2,stroke:#e65100
    class A,B,C,D,E,G ok
    class F1,F2,F3,F4,F5,F6,F7 fail

关键在失败结点的查找长度怎么数。 教材原话：「这些失败结点是我们虚构的空结点，实际上是不存在的，所以到达失败结点时所查找的长度等于它上面的一个圆形结点的所在层数」。写成式子就是 ：

不成功

时为 ，比一般顺序查找的 好一些。

边界辨析：

有序线性表的顺序查找，成功 与一般线性表完全相同，仍是 。 有序性只在失败时帮上忙。看到「有序」两个字就把成功的 也改小，是这一节最常见的错。

分子里为什么末尾是「」而不是「」：最右边那两个失败结点 和 挂在同一个圆形结点 60 下面，层数相同，所以最大的那一项出现了两次。

两个「顺序」不是一回事

教材专门加了一段：

注意，有序线性表的顺序查找和后面的折半查找的思想是不一样的，且有序线性表的顺序查找中的线性表可以是链式存储结构，而折半查找中的线性表只能是顺序存储结构。

这是 7.2 全节最值得记的一句。 「有序」和「随机存取」是两个独立的条件：顺序查找只要前者，折半查找两个都要。

分块查找

也称索引顺序查找。把查找表分成若干块：

  • 块内的元素可以无序
  • 块间的元素是有序的：第一块中的最大关键字小于第二块中所有记录的关键字，以此类推

再建一个索引表，索引表中每个元素含各块的最大关键字和各块中第一个元素的地址，索引表按关键字有序排列。

flowchart TD
    subgraph IDX["索引表（有序）"]
        I1["最大关键字 24<br/>起始地址 1"]
        I2["最大关键字 54<br/>起始地址 7"]
        I3["最大关键字 78<br/>起始地址 10"]
        I4["最大关键字 88<br/>起始地址 13"]
    end
    subgraph BLK["查找表（块内无序，块间有序）"]
        B1["24 21 6 11 8 22"]
        B2["32 31 54"]
        B3["72 61 78"]
        B4["88 83"]
    end
    I1 --> B1
    I2 --> B2
    I3 --> B3
    I4 --> B4

    classDef idx fill:#c8e6c9,stroke:#1b5e20
    classDef blk fill:#e3f2fd,stroke:#1565c0
    class I1,I2,I3,I4 idx
    class B1,B2,B3,B4 blk

查找分两步：① 在索引表中确定待查记录所在的块，可以顺序查找也可以折半查找索引表；② 在块内顺序查找。

将长度为 的表均匀地分为 块、每块 个记录，等概率下若索引表和块内均采用顺序查找：

此时若 ，则 取最小值 。

边界辨析：

第二步只能是顺序查找，因为块内无序。 只有第一步（索引表）才可以折半。 题目问「分块查找能否对块内折半」，答案是不能——除非题目额外说明块内也有序。

索引表用折半查找时有一个必然的推论：索引表存的是各块的最大关键字，所以当折半查找在索引表中没有找到相等项而结束时，待查关键字应落在 low 所指的那一块里——因为该块的最大关键字是第一个不小于待查值的。取 high 所指的块会偏小一块。

手算模板

顺序查找类：

  1. 判断是「一般」还是「有序」：只影响不成功。
  2. 成功一律 （等概率）。
  3. 不成功：一般是 ；有序画判定树，失败结点取其父结点的层数。

分块查找：

  1. 分清 （块数）和 （块长），。
  2. ：索引表顺序查找 ；折半查找按 的判定树算。
  3. ：块内只能顺序，。
  4. 相加。要最小值就令 ，答案 。

边界

说法判断说明
「顺序查找只适用于顺序表」❌顺序存储或链式存储皆可，对有序性也无要求
「链表可以用折半查找」❌折半要求随机存取，链表只能顺序查找
「有序线性表的顺序查找比一般的成功更快」❌成功完全一样，只有不成功变快
「哨兵能减少比较次数」❌减少的是边界判断，比较次数不变
「哨兵放在 ST.elem[0]，所以下标 0 存数据」❌下标 0 专门空出来放哨兵，数据从 1 开始
「分块查找要求块内有序」❌块内无序、块间有序。有序的是索引表和块之间
「分块查找块内可以折半」❌块内无序，只能顺序查找
「索引表存各块的第一个关键字」❌存各块的最大关键字和第一个元素的地址
「分块查找的 最小值是 」❌是 ，在 时取到

口径差异：

算法竞赛里的「分块」是一种暴力优化技巧（块长取 、块内维护前缀和或有序副本）， 目标是让修改和查询都摊到 。王道的分块查找块内是无序的、不维护任何附加信息， 考的是 这个两段式的加法，不是复杂度分析。 块长取 这个结论两边一样，但推导它的式子完全不同。

对照速查

方法成功不成功
一般线性表顺序查找
有序线性表顺序查找
分块查找（均分、两段都顺序）—
分块查找最优（）—
条件顺序查找折半查找分块查找
要求有序否是块间是，块内否
要求顺序存储否是索引表是
支持动态增删是代价 是（插到对应块即可）
时间量级

考点

  • 顺序查找对存储结构和有序性都无要求——这是它唯一的优点，也是选择题的常客。
  • 有序线性表的顺序查找：成功不变、失败变快，以及失败结点取父结点层数。
  • 哨兵的作用是省边界判断，返回 0 表示失败。
  • 折半只能顺序存储、链表只能顺序查找，一句话两个方向都要能答。
  • 分块查找块内无序，第二步不能折半。
  • 时 最小为 。

链接

反向链接