核心概述
分数二分（Stern–Brocot/Farey 二分）：在有理数域上对单调谓词进行二分搜索，使用“中项” m = (a+c)/(b+d) 在两端点 a/b 与 c/d 间逼近，不用浮点且比较稳定；亦可在分母受限时求最优逼近。典型复杂度 O(log 范围)。
原文引述
Description: Binary search on rationals via Stern–Brocot/Farey mediants. Maintains bounds L=a/b and R=c/d; tests mediant m=(a+c)/(b+d) with a monotone predicate without floating-point. Also finds best approximation under denominator bounds. Time: O(log range) predicate calls Status: tested
展开阐述
-
接口/约定（据实现）
- sternBrocotSearch(predicate, L=(0/1), R=(1/0)) → p/q：在 (L,R) 内找使 predicate(p/q) 成立的最小/最大分数（按需要选择更新规则）。
- bestWithDenBound(x, maxQ) → p/q：在 0/1..1/0 范围内，找分母 q ≤ maxQ 时最贴近实数 x 的分数（可用连分数或以 Stern–Brocot 配合“成倍跳”实现）。
- 比较无需浮点：a/b ? c/d 等价于 a·d ? c·b（用 128 位避免溢出）。
-
核心思路（中项 + 单调）
- 维护左界 L=a/b 与右界 R=c/d（初始可取 0/1 与 1/0 表示 −∞ 与 +∞）。
- 取中项 m = (a+c)/(b+d)（Farey 中项/mediant），满足 L < m < R。
- 若 predicate(m) 为真（例如 m 足够大/满足门槛），则 R ← m；否则 L ← m。
- 重复至达到目标精度、步数上限、或命中答案的离散条件（如最小满足分数）。
- 为避免步进过细，可采用“倍增步长”法：在固定方向连续倍增 k，使 b+d 在限内，随后回退一步进入另一侧。
-
分母受限最优逼近
- 目标：在 q ≤ Q 的约束下，使 |x − p/q| 最小。
- 方法一：连分数（见 080-数论-连分数）生成收敛分数与半收敛，在线性时间内得到答案。
- 方法二：Stern–Brocot：在树上按 x 的相对位置移动（比较 x 与 m），并用“跳步”控制使分母不超过 Q；当即将超限时，取最后一步的最优线性组合得到最接近分数。
-
输出语义
- 返回分数 p/q（约分后），满足给定谓词边界（最小/最大）或在分母上界下的最佳逼近。
- 保证严格有序与无重复；全程整型比较，避免浮点误差。
-
复杂度
- 每次中项都会增大分母（b+d），对固定精度或上界 Q，迭代次数 O(log Q)～O(log 范围)。
- 单次谓词/比较为 O(1)（大整数则视位数）。
-
使用与注意
- 溢出：比较与构造中项用 128 位（或大整数）进行 a·d 与 c·b、a+c、b+d 的计算。
- 单调性：predicate 必须关于有理数单调（如 m ≥ 目标阈值），否则二分不成立。
- 终止条件：依据精度阈值、分母上界、或命中离散最优（如最小满足 p/q）。
- 若仅需最佳有理逼近，优先使用连分数；Stern–Brocot 更适合“带单调谓词”的搜索或在线构造。