第七单元：二分查找 · 猜数博弈与折半逼近

封神冰川的深处，狡猾的谜语者（Riddler）心里想了一个 1 到 999 之间的数字，只给你 10 次机会去猜中它。每猜一次，他会用召唤怪物的方式暗示你"猜大了"还是"猜小了"。999 个可能、10 次机会——如果一个一个地试，永远也来不及。这一单元你将掌握计算机科学里最优雅、最重要的搜索算法之一：二分查找（binary search）。它的威力惊人——哪怕有一百万个数字，它也能在 20 次以内锁定答案。

7.1.1 什么是二分查找（What Is Binary Search）

7.1.1.1 "折半+排除"的猜数策略 A halve-and-eliminate strategy

二分查找是一种在有序范围里快速定位目标的算法。它的名字里"二分"就是"一分为二"的意思：每一步都猜正中间的那个数，然后根据"太大/太小"的提示，果断丢掉一半不可能的区间，只在剩下的一半里继续找。就这样一半、一半地砍，范围飞快地缩小，很快就只剩下目标本身。

7.1.2 为何比逐个猜快（Why It Beats Guessing One by One）

7.1.2.1 线性 vs 二分：天壤之别 Linear vs binary: a huge difference

如果从 1 开始一个一个往上猜（线性查找），最坏情况要猜 999 次。而二分查找每次把范围减半，999 → 500 → 250 → 125 → … 只需约 10 次 就能覆盖全部 999 个数字。这就是关卡只给 10 次机会、却依然稳赢的原因——它逼着你使用二分查找。

7.2.1 每次砍掉一半（Cut the Range in Half）

7.2.1.1 用两个边界圈定"还可能的范围" Track the range with two borders

二分查找要时刻记住"目标还可能在哪个范围内"。我们用两个变量描述这个范围：下边界 lowBorder 和上边界 highBorder。开始时目标可能是 1 到 999 中任意一个，所以把边界设在范围之外——lowBorder = 0、highBorder = 1000（即 lowestPossible-1 与 highestPossible+1）。每次猜完，就把其中一个边界往中间挪，范围随之缩小。

# 初始化：把边界设在可能范围的两侧之外
lowestPossible = 1
highestPossible = 999
lowBorder = lowestPossible - 1     # 0，比最小值还小
highBorder = highestPossible + 1   # 1000，比最大值还大

7.2.2 取中点公式（The Midpoint Formula）

7.2.2.1 猜就猜正中间 Always guess the middle

每一次都猜当前区间的正中间，才能保证无论目标偏大还是偏小，被排除掉的都恰好是一半。中点的算法是"下边界加上区间长度的一半"：guess = int(lowBorder + (highBorder - lowBorder) / 2)。用 int() 是因为猜测必须是整数，而除以 2 可能得到小数。

7.3.1 scout 与 munchkin（The Two Ogre Types）

7.3.1.1 谜语者用怪物类型给暗示 The Riddler hints via ogre type

谜语者不直接说话，而是每次召唤一只怪物来暗示。规则是：如果出现的是侦察兵（scout），说明真正的数字比你猜的更大（greater）；如果出现的是Munchkin 食人魔，说明真正的数字比你猜的更小。你要先用 enemy.type 读出怪物类型，再据此判断该往哪个方向调整。

7.3.2 太大还是太小（Too High or Too Low）

7.3.2.1 用 enemy.type 分支决定方向 Branch on enemy.type to pick a direction

读出怪物类型后，用 if / elif 分两种情况处理。侦察兵表示目标更大，那说明"我们猜的这个数太小了"，可以把它作为新的下边界；Munchkin 表示目标更小，说明"这个数太大了"，把它作为新的上边界。

# 根据怪物类型判断猜大了还是猜小了
if enemy.type == "scout":     # 目标更大 → 猜小了
    lowBorder = guess           # 抬高下边界
elif enemy.type == "munchkin":   # 目标更小 → 猜大了
    highBorder = guess          # 压低上边界

7.4.1 移动上下边界（Moving the Borders）

7.4.1.1 把刚才的猜测变成新边界 Turn the last guess into a new border

调整区间的关键动作，就是把"这次的猜测 guess"赋值给某个边界。猜小了（scout）就 lowBorder = guess，意思是"目标一定大于 guess，所以下界抬到这里"；猜大了（munchkin）就 highBorder = guess，意思是"目标一定小于 guess，上界压到这里"。这样每次都把不可能的那一半永久排除。

7.4.2 区间不断收缩（The Range Keeps Shrinking）

7.4.2.1 收缩到只剩一个数即命中 Shrink until only the answer remains

每一轮"猜中点 → 看怪物 → 移边界"都会让区间缩小一半。随着 lowBorder 和 highBorder 越来越接近，中点也越来越逼近真正的数字。当区间收缩到只剩一个可能值时，那个中点就正是谜语者藏的数字——命中，胜利！

7.5.1 对数级次数（Logarithmic Number of Tries）

7.5.1.1 为什么 10 次就够 Why 10 tries are enough

每次减半，意味着 N 个数字最多需要 log₂(N) 次就能锁定。999 个数字，log₂(999) ≈ 9.96，向上取整就是 10 次——这正是关卡给你 10 次机会的原因，不多不少。这种"次数随规模只对数级增长"的特性，让二分查找即便面对海量数据也快得惊人。

7.5.2 逐帧节奏：先打怪再猜（Beat the Ogre, Then Guess）

7.5.2.1 每轮之间要先清场 Clear the ogre before the next guess

关卡有个特别的节奏：每次猜测召唤的怪物，必须先被击败，你才能进行下一次猜测。所以主循环里要判断——如果场上有敌人，就先根据它的类型调整边界、再攻击它；如果没有敌人，才计算新中点并说出猜测。这样"猜一次 → 打一次"交替进行，直到猜中。

这一节聚焦关卡的策略、思路与算法设计，只展示用于说明的关键片段，完整通关程序请你自己动手完成。

第 16 关 · 猜猜我的数字

❄️ 猜猜我的数字 —— 10 次机会破解谜语者

图2：猜猜我的数字——谜语者想了 1~999 的数字，每次猜测召唤 scout（太小）或 munchkin（太大）暗示，10 次内用二分查找命中

策略：用二分查找把 999 个可能压进 10 次

谜语者臭名昭著地爱撒谎，但他无法违背"更大/更小"这条规则——这就是我们的突破口。策略只有一个：永远猜当前区间的正中间。每次猜测都恰好排除一半可能，10 次减半足以从 999 个数字里锁定唯一答案。这是一场"用算法碾压运气"的博弈。

思路拆解一：初始化两个边界

先设定搜索范围。可能值是 1~999，但边界要设在范围之外：lowBorder = lowestPossible - 1（0）、highBorder = highestPossible + 1（1000）。这样取中点时才能覆盖到 1 和 999 两个端点，不会因边界卡死而漏掉答案。

# 关键片段：把边界设在可能范围两侧之外
lowestPossible = 1
highestPossible = 999
lowBorder = lowestPossible - 1       # 0
highBorder = highestPossible + 1     # 1000

思路拆解二：有敌人就"读暗示 + 移边界 + 清场"

主循环每轮先看场上有没有怪物。若有，说明这是对上一次猜测的反馈：读 enemy.type，是 scout 就抬 lowBorder、是 munchkin 就压 highBorder，然后 hero.attack 击败它腾出下一次猜测的机会。移边界必须在攻击前或攻击时完成，否则怪物消失后就读不到暗示了。

# 关键片段：根据怪物类型调整区间，再清场
enemy = hero.findNearest(hero.findEnemies())
if enemy:
    if enemy.type == "scout":       # 目标更大 → 猜小了
        lowBorder = guess
    elif enemy.type == "munchkin":   # 目标更小 → 猜大了
        highBorder = guess
    hero.attack(enemy)                  # 击败后才能继续猜

思路拆解三：没敌人就算新中点并说出

当场上清空、没有怪物时，就该发起新一轮猜测：用取中点公式算出当前区间正中间的整数 guess，再 hero.say(guess) 把它喊给谜语者。喊完谜语者会召唤新怪物暗示——循环回到上一步继续收缩区间。

# 关键片段：没敌人时，猜当前区间的正中间
else:
    guess = int(lowBorder + (highBorder - lowBorder) / 2)
    hero.say(guess)

为什么这套结构能赢：整个循环就是"猜中点 → 打怪读暗示 → 移边界 → 再猜中点"的不断重复。因为每次都猜正中间，无论谜语者的数字偏哪边，都能排除一半——10 轮足以把 999 个可能收缩到 1 个。谜语者再怎么"骗"，也逃不出他自己定下的"更大/更小"规则。

guess 要先有值：第一轮循环时若先进入"有敌人"分支去用 guess，而 guess 还没被赋过值，程序会报错。实际关卡里第一帧通常没有敌人，会先走 else 分支算出首个 guess；但严谨起见，可在循环外给 guess 一个初始中点值。

7.7.1 新手最容易踩的坑（Pitfalls for Beginners）

7.7.1.1 二分查找的典型问题 Typical issues with binary search

图3：方向记反、忘取整、边界设错、先攻击后读类型，是本单元最常见的失误