浮点数二分怎么写？为什么不能只用 left <= right？

简化版

浮点数二分通常按精度控制循环，而不是用整数二分里的 left <= right。

常见写法是循环固定次数，或者当 right - left > eps 时继续。因为浮点数是连续近似值，不存在简单的 mid + 1 或 mid - 1，也容易受到精度误差影响。

写浮点二分时，关键是确定单调性、精度 eps 和返回左边界还是右边界。

详细版

整数二分可以通过 mid + 1、mid - 1 丢掉中点。

浮点二分不能这样写：

if check(mid):
  right = mid
else:
  left = mid

循环条件通常是：

while right - left > eps

或者固定迭代 60 到 100 次。

写法	特点
right - left > eps	精度直观
固定次数	避免浮点边界死循环

适合求平方根、最小半径、连续答案空间上的最优值。

完整版教学

1. 浮点二分和整数二分的差别

整数二分的搜索空间是离散的。

例如：

0, 1, 2, 3, 4

浮点二分的搜索空间是连续区间：

[0.0, 10.0]

中间有无穷多个可能值，所以不能用 mid + 1 这种方式跳过中点。

2. 为什么不能简单写 left <= right

浮点数存在精度表示问题。

如果写：

while left <= right

并且更新为：

left = mid
right = mid

当区间非常小时，mid 可能因为精度限制等于 left 或 right，循环无法继续收缩。

浮点二分要靠精度阈值或固定次数停止，而不是等待左右边界交错。

3. eps 写法怎么理解

eps 是允许误差。

while right - left > eps:
  mid = (left + right) / 2

当区间长度小于 eps，说明答案已经被压缩到足够小的范围内，可以返回 left、right 或中点。

常见 eps：

要求	eps
1e-5 精度	1e-6 或更小
输出 6 位小数	1e-7 常见
几何题	根据题目误差

4. 固定次数为什么可行

每次二分都会把区间长度减半。

经过 k 次后，区间长度是：

initialRange / 2^k

如果迭代 100 次，对 double 来说通常已经非常精确。

所以竞赛和面试里经常写：

for iter in 1..100:
  mid = (left + right) / 2

这种写法能避免某些浮点死循环。

5. check 函数仍然要单调

浮点二分依然要求答案空间具有单调性。

例如求最小半径 r：

半径 r 可行 -> 更大的半径也可行

这就可以二分最小可行半径。

如果 check(mid) 不单调，二分没有意义。

6. 返回 left、right 还是 mid

如果用 while right - left > eps，结束后 left 和 right 已经很接近。

通常返回：

(left + right) / 2

如果题目是最小可行值，也可以返回 right；如果是最大可行值，可以返回 left。

目标	常见返回
近似数值	中点
最小可行	right
最大可行	left

7. mid 是否需要防溢出

整数二分常写：

mid = left + (right - left) / 2

浮点二分也可以这样写。虽然浮点范围大，但这样写仍然更稳，特别是边界值很大时。

不要因为是浮点就忽略数值稳定性。

8. 常见误区与追问

• 误区：浮点二分也用 left <= right。 浮点空间连续且有精度误差，应使用 eps 或固定迭代次数。
• 误区：浮点二分可以用 mid + 1。 浮点没有离散步长，不能这样更新。
• 误区：只要是数值题都能二分。 仍然需要 check 函数具备单调性。
• 追问：为什么固定 100 次够？ 每次区间减半，100 次对 double 精度通常绰绰有余。
• 追问：返回 left 还是 right？ 看要找最大可行还是最小可行，普通近似值返回中点也可以。