高楼扔鸡蛋：二分查找为什么不是最优？
一句话结论（30s）
结论先行：2 个鸡蛋 100 层楼，最坏情况最少 14 次测试。本质是动态规划的”均匀分配风险”——因为二分查找让第一个鸡蛋在最坏情况下碎得太早，剩余楼层全得靠第二个鸡蛋逐层测，所以最优策略要让第一个鸡蛋每次跳层后为最坏情况预留的测试次数保持一致。
核心原理（2min）
设最坏允许 x 次操作，让第一个鸡蛋依次在第 x、x+(x-1)、x+(x-1)+(x-2)… 层扔，每次缩一层。第一个鸡蛋第 k 次才碎时，第二个鸡蛋只需在确定的小范围内测至多 k-1 次，二者相加恒等于 x，于是总测试预算被平均分配到每次尝试。累计覆盖楼层 x+(x-1)+…+1 = x(x+1)/2 ≥ 100，解得 x=14。通解是 DP：dp[k][n] = min max(dp[k-1][x-1], dp[k][n-x]) + 1，鸡蛋足够多（K ≥ log₂N）时退化为二分查找。
底层深入（5-10min）
问题
2 个鸡蛋，100 层楼。鸡蛋从某一层开始会碎，以下是安全的。最少多少次测试（最坏情况）能找到临界层？
为什么二分查找是 50 次？
二分查找从第 50 层开始扔：碎了 → 第 2 个鸡蛋必须从 1 到 49 逐层测（49 次）→ 最坏 50 次。第一个鸡蛋在 50 层碎是最坏情况——之后需要测 49 层。
💭 思考：为什么”鸡蛋会碎”这件事就让二分失效？——因为二分假设每次都能继续减半，但第一个鸡蛋一旦碎了就没有了，剩余的楼层只能靠唯一剩下的第二个鸡蛋一层层测，最坏情况把”减半”的优势全部抵消，反而退化成线性 50 次。
最优策略：$x(x+1)/2 \ge 100$
假设第一个鸡蛋依次在第 $x, x+(x-1), x+(x-1)+(x-2), \ldots$ 层扔，每次缩小一层。
如果在第 $k$ 次扔时碎掉，已经确定了一个较小的范围（上一次安全层到当前层），且第二个鸡蛋需要测至多 k-1 次。关键洞察：让第一个鸡蛋的每次测试”最坏情况下需要多少后续测试”保持一致。
设最坏情况允许 $x$ 次操作：
$$x + (x-1) + (x-2) + \cdots + 1 \ge 100$$ $$x(x+1)/2 \ge 100$$ $$x \ge 14$$
最优策略：第一个鸡蛋依次在第 14, 27 (14+13), 39 (14+13+12), 50, 60, 69, 77, 84, 90, 95, 99, 100 层扔。
如果在第 14 层碎了 → 第二个鸡蛋从 1 测到 13 → 最多 14 次。如果在第 27 层碎了 → 第二个鸡蛋从 15 测到 26 → 已经用了 2 次（14+27），还需 12 次 = 14 次。
每次第一个鸡蛋测试失败后，后续所需的最坏测试次数都是一样的——14 次。这就是最优策略。
💭 思考：为什么第一个鸡蛋每次跳层要”缩一层”？——为了均衡：第一次若碎，第二个鸡蛋要测 x-1 层，所以第一次最多跳 x 层；第二次若碎，第二个鸡蛋只测 x-2 层，所以第二次可跳 x-1 层……这样”跳的层数 + 之后要补测的层数”恒等于 x，把最坏情况的预算均匀分给每一次。
通解：K 个鸡蛋 N 层楼
$$dp[k][n] = \min_{1 \le x \le n} {\max(dp[k-1][x-1], dp[k][n-x]) + 1}$$
$x$ 是第一个鸡蛋扔的楼层。碎了（$dp[k-1][x-1]$）= 用 k-1 个蛋测下面的 x-1 层；没碎（$dp[k][n-x]$）= 用 k 个蛋测上面的 n-x 层。取两者最大的最坏情况 + 此次测试。
$K=2$ 时，最优解就是上面的 $x(x+1)/2$ 公式。$K$ 足够大（$K \ge \log_2 N$）时，退化为二分查找——鸡蛋充足，直接二分。
💭 思考：为什么 DP 里既取 max 又取 min？——取 max 是处理最坏情况（碎与不碎哪个分支更糟）；取 min 是我们在所有可选楼层 x 中挑一个让最坏情况最小的 x，这就是”最坏情况下求最优”的双层优化。
总结
二分查找在”鸡蛋无限”时最优（每次减半）。鸡蛋有限时，需要在”第一个鸡蛋跳多少层”和”第二个鸡蛋测多少层”之间找平衡——跳太少浪费鸡蛋，跳太多浪费机会。最优策略让每次测试为最坏情况预留的测试次数相同——这是动态规划问题中”均匀分配风险”的通用原则。
章末提问
追问 1：为什么二分查找在这里不是最优？
回答思路：结论是鸡蛋会碎，第一个鸡蛋若在中间层碎了，剩下的楼层只能靠唯一第二个鸡蛋逐层测，最坏退化成线性；所以鸡蛋有限时”每次减半”的假设不成立，必须为第二个鸡蛋预留测序预算。
追问 2：x(x+1)/2 ≥ 100 这个公式怎么来的？
回答思路：结论是让第一个鸡蛋第 1 次跳 x 层、第 2 次跳 x-1 层……每跳一次缩一层，累计覆盖楼层是 x+(x-1)+…+1=x(x+1)/2，要求覆盖满 100 层即得 x≥14，且每次失败后补测次数恒定，保证最坏情况统一。
追问 3：鸡蛋数足够多时，最优策略会退化成什么？
回答思路：结论是退化为二分查找，因为鸡蛋充足时第一个鸡蛋每次都可放心减半、不必为第二个鸡蛋预留，每次测试覆盖范围最大化，最坏次数就是 log₂N。