考研笔记

折半查找

折半查找也称二分查找，它仅适用于有序的顺序表。

这一节的分量不在算法——算法三行就写完了——而在判定树。判定树把「查找过程」变成一棵确定的树，之后所有的问题（比较多少次、 多大、某个序列是否可能是查找路径）就都变成了在树上数结点。

判定树还是本章的一个枢纽：它是一棵 平衡二叉树（教材原文），失败结点的处理方式又被 B 树 和 红黑树 沿用（都要虚构 个外部结点）。先在这里把「圆形结点 / 方形结点」这套语言学会，后面三节省一半力气。

机制

算法与取整约定

int Binary_Search(SSTable L, ElemType key){
    int low = 0, high = L.TableLen - 1, mid;
    while(low <= high){
        mid = (low + high) / 2;        //取中间位置
        if(L.elem[mid] == key)
            return mid;                //查找成功则返回所在位置
        else if(L.elem[mid] > key)
            high = mid - 1;            //从前半部分继续查找
        else
            low = mid + 1;             //从后半部分继续查找
    }
    return -1;                         //查找失败，返回 −1
}

教材专门交代了一条约定：

当折半查找算法选取中间结点时，既可以采用向下取整，又可以采用向上取整。但每次查找的取整方式必须相同。

「必须相同」才是考点。 取整方式不同会生成不同的判定树， 也随之不同。题目若不说明，默认向下取整（即上面代码里的 (low+high)/2）。

判定树

折半查找的过程可用一棵二叉树描述，称为判定树：

  • 圆形结点表示一个记录，结点中的值为该记录的关键字值
  • 树中最下面的叶结点都是方形的，表示查找失败的区间
  • 有序序列有 个元素，则判定树有 个圆形的非叶结点和 个方形的叶结点
  • 每个结点值均大于其左子结点值，且均小于其右子结点值——判定树本身就是一棵二叉排序树
  • 判定树是一棵平衡二叉树

以 11 个元素的有序表 为例（教材图 7.2）：

flowchart TD
    R((29)) --- A((13))
    R --- B((37))
    A --- A1((7))
    A --- A2((16))
    B --- B1((32))
    B --- B2((41))
    A1 --- F1["(−∞,7)"]
    A1 --- A1R((10))
    A2 --- F2["(13,16)"]
    A2 --- A2R((19))
    B1 --- F3["(29,32)"]
    B1 --- B1R((33))
    B2 --- F4["(37,41)"]
    B2 --- B2R((43))
    A1R --- G1["(7,10)"]
    A1R --- G2["(10,13)"]
    A2R --- G3["(16,19)"]
    A2R --- G4["(19,29)"]
    B1R --- G5["(32,33)"]
    B1R --- G6["(33,37)"]
    B2R --- G7["(41,43)"]
    B2R --- G8["(43,+∞)"]

    classDef ok fill:#e3f2fd,stroke:#1565c0
    classDef f3 fill:#ffe0b2,stroke:#e65100
    classDef f4 fill:#ffcdd2,stroke:#b71c1c
    class R,A,B,A1,A2,B1,B2,A1R,A2R,B1R,B2R ok
    class F1,F2,F3,F4 f3
    class G1,G2,G3,G4,G5,G6,G7,G8 f4

橙色的 4 个失败结点查找长度为 3，红色的 8 个为 4——两种颜色对应下面式子里的两项。

两种查找长度的数法

教材原文，一字都不能改：

  • 查找成功时的查找长度为从根结点到目的结点路径上的结点数
  • 查找失败时的查找长度为从根结点到对应失败结点的父结点路径上的结点数

于是在上图中，等概率情况下

成功不成功

边界辨析：

成功数到自己，失败数到父亲。 失败结点本身不参与计数，因为它是虚构的、实际不存在的空结点—— 到达它意味着上一次比较已经结束了。 两个式子的分母也不同：成功是 ，失败是 。

高度与复杂度

用折半查找法查找到给定值的比较次数最多不会超过树的高度。元素个数为 时树高

等概率查找成功时

时间复杂度 。

注意 这个式子与完全二叉树的高度公式同形——因为判定树是平衡二叉树，形状上就是把 个结点尽量摊平。

为什么只能用顺序存储

教材给出的理由是一句因果，不是规定：

因为折半查找需要方便地定位查找区域，所以它要求线性表必须具有随机存取的特性。因此，该查找法仅适合于顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列。

「有序」和「随机存取」是两个独立的条件，缺一不可。 有序的链表用不了折半（不能随机存取），无序的数组也用不了（不满足有序）。这一条与 7.2.1 里「有序线性表的顺序查找可以是链式」正好对照着记。

手算模板

给定有序表画判定树：

  1. 从整个区间 开始，，该位置的元素作根。
  2. 左区间 递归成左子树，右区间 递归成右子树。
  3. 空区间落成一个方形失败结点，共 个。
  4. 标层：根为第 1 层。

算两个 ：

数什么分母
成功每个圆形结点所在层数
不成功每个方形结点父结点所在层数失败结点数

判断某序列能否是折半查找的查找路径（2015、2017 考过）：沿路径逐个验证——每一步的 mid 必须由当时的 按同一取整规则算出，且比较结果要与序列的走向一致。只要有一步的 mid 对不上就否定。

边界

说法判断说明
「折半查找可用于有序链表」❌要随机存取，链表不行
「折半查找可用于无序数组」❌必须有序
「mid 只能向下取整」❌向上也可以，但每次必须相同
「取整方式不影响 」❌生成不同的判定树， 不同
「失败结点也算一次比较」❌失败的查找长度数到父结点为止
「不成功的 除以 」❌除以
「判定树是完全二叉树」⚠️教材说的是平衡二叉树。形状很接近，但完全二叉树是更强的条件，不要替换
「 个元素的判定树有 个结点」❌ 个圆形非叶结点 个方形叶结点
「折半查找的判定树不唯一」❌取整规则一定后判定树唯一——这正是它与 二叉排序树 的根本差别
「折半查找一定比顺序查找快」❌概率不均时不一定（教材 7.2 试题解析给过反例：按概率降序排的顺序查找可以更优）

口径差异：

算法竞赛写的二分几乎都是 lower_bound 式的边界二分：循环里不判相等， 一直收缩到区间只剩一个位置再检查。它的比较次数恒为 ，与元素位置无关。 王道的 Binary_Search 一相等就 return，所以浅层的元素比较次数少、深层的多—— 成功 这个量只在「提前返回」的版本里才有意义。 按算竞的边界二分去理解这一节，会觉得「每个元素的查找长度不都一样吗」，从而整节读不进去。

关联对照：

判定树唯一，二叉排序树不唯一。 同一组关键字，折半查找的判定树被取整规则唯一确定； 而二叉排序树的形态取决于插入顺序（7.3.1 图 7.8 就是同一组关键字的两棵不同 BST）。 教材因此说「就平均时间性能而言，二叉排序树上的查找和二分查找差不多」，差不多，但一个是确定的、一个是碰运气的。

对照速查

量式子
树高
成功 ASL
时间复杂度
圆形结点数
方形结点数
结点形状含义查找长度数到哪
圆形表中真实存在的记录自己所在层
方形虚构的失败区间父结点所在层

考点

  • 判定树的构造与两个 的分别计算（分母不同）。
  • 失败的查找长度数到父结点。
  • 取整方式必须每次相同，且影响判定树形状。
  • 只能顺序存储 + 必须有序，两个条件的独立性。
  • ，最多比较次数不超过树高。
  • 判断给定序列能否为折半查找路径（2015、2017）。
  • 判定树是平衡二叉树，且形态唯一。

链接

反向链接