【浮点数二分】LeetCode 3453. 分割正方形 I

前言

零点定理：如果函数 \(f(x)\) 在闭区间 \([a, b]\) 上连续，且 \(f(a) \times f(b) < 0\)（即函数在两端点值异号），则在开区间 \((a, b)\) 内至少存在一点 \(c\)，使得 \(f(c) = 0\)。

零点定理是连续函数的一个重要性质，也是二分法求根的理论基础。

题目

https://leetcode.cn/problems/separate-squares-i/description/

题解

浮点数二分用于在连续区间中查找满足条件的实数解。与整数二分不同，它通过精度控制而非整数边界来判断循环结束。

浮点数二分编码有两种方法：

1. 固定迭代次数法（推荐）
2. 精度控制法

关于浮点数二分的编码，更推荐使用固定次数迭代法，可以更好地避免死循环。固定次数迭代法核心点在于求出迭代次数，以下讲解如何求解迭代次数：

以左边界 \(l=1\)，右边界 \(r = 10^9\) 为例，要求答案精度控制在 \(10^{-5}\) 内为案例。
设二分 \(x\) 次，可以使得区间大小不超过 \(10^{-5}\)，那么可列出以下方程：$$\frac{r-l+1}{2^x} \leq 10^{-5}$$
化简，可得：$$x \geq log_2{\frac{r-l+1}{10^{-5}}} = log_2 10^{14} \approx 46.5$$
因此，以左边界 \(l=1\)，右边界 \(r = 10^9\)，要求答案精度控制在 \(10^{-5}\) 内至多只需要固定迭代 \(47\) 次即可做到。

// 方法1：精度控制法
double binary_search_double(double l, double r, double eps = 1e-8) {while (r - l > eps) {  // 当区间大于精度要求时继续double mid = (l + r) / 2;if (check(mid)) {  // check函数需要根据具体问题实现r = mid;  // 解在左半区间} else {l = mid;  // 解在右半区间}}return l;  // 或 (l + r) / 2
}// 方法2：固定迭代次数法（避免无限循环）
double binary_search_double_iter(double l, double r, int iter = 100) {for (int i = 0; i < iter; i++) {double mid = (l + r) / 2;if (check(mid)) {r = mid;} else {l = mid;}}return l;
}

参考代码

class Solution {
public:double separateSquares(vector<vector<int>>& squares) {double tot = 0, mx = 0;for (auto &sq: squares) {tot += 1.0 * sq[2] * sq[2];mx = max(mx, 1.0 * sq[1] + sq[2]);}double le = 0, ri = mx, md;auto check = [&]() -> bool {double sum = 0;for (auto &sq: squares) {if (sq[1] > md) continue;double up = sq[1] + sq[2];sum += 1.0 * sq[2] * (min(md, up) - sq[1]);}return sum >= tot / 2;};for (int i = 0; i < 47; ++ i) {md = (le + ri) / 2.0;(check() ? ri : le) = md;}return (le + ri) / 2.0;}
};