二分查找精度

直观推导：从"切蛋糕"开始

想象你有一个长度为 1 的区间，你要用二分法把它切成更小的段：

规律一目了然：n 次迭代后，每段长度是 1/2^n

核心问题：精度要达到多少？

题目要求精度是 1/M（M=100000），意思是：最终误差不能超过 1/100000

所以我们要保证：

每段长度 ≤ 1/M

代入上面的规律：

1/2^n ≤ 1/M

两边取倒数：

2^n ≥ M

反证验证

假设 2^n < M 会怎样？

比如 M=8（要求精度 1/8），如果只迭代 2 次：

• 2^2 = 4 < 8
• 精度是 1/4，远达不到 1/8

必须迭代到 n=3：

• 2^3 = 8 ≥ 8
• 精度刚好是 1/8，满足要求

对数换算

从 2^n ≥ M 可以推导出：

n ≥ log₂(M)

因为：

• 如果 M=8，log₂(8) = 3，需要 3 次迭代
• 如果 M=100000，log₂(100000) ≈ 16.6，需要 17 次迭代

而 .bit_length() 正是计算 ⌈log₂(M)⌉（向上取整）的最快方式。

总结

为什么要满足 2^n ≥ M？

因为这是二分查找精度的物理极限：

• n 次迭代最多只能把区间分成 2^n 段
• 每段长度（即最大误差）是 1/2^n
• 要让误差 ≤ 1/M，必须让 1/2^n ≤ 1/M
• 等价于 2^n ≥ M

这是数学规律，不是人为选择的。二分查找的"每次折半"机制，注定了它的精度与迭代次数呈指数关系。