二分法

二分法（bisection method），又称对分法、折半法，是一种在数学和计算机科学中广泛应用的数值方法，主要用于求解形如 f(x)=0 的连续函数方程的近似根。其理论基础源于连续函数的零点定理（Bolzano 定理）：如果函数 f(x) 在闭区间 [a,b] 上连续，且 f(a) 与 f(b) 异号（即 f(a)·f(b)<0），则至少存在一点 c∈(a,b) 使得 f(c)=0。二分法通过每次将区间二等分，并检查中点函数值的符号，确定零点所在的子区间，从而逐步缩小搜索范围。

算法流程

给定连续函数 f(x) 和初始区间 [a,b]（满足 f(a)·f(b)<0），预设误差阈值 ε。具体步骤如下：

• 计算中点 m = (a+b)/2。
• 如果 |b-a|<ε 或 f(m)=0，则停止并输出 m 作为近似根。
• 否则根据 f(a) 与 f(m) 的符号：若 f(a)·f(m)<0，则零点在 (a,m) 内，令 b=m；否则零点在 (m,b) 内，令 a=m。
• 重复上述过程直至满足精度要求。

程序实现示例

以下为 C 语言实现二分法的典型代码，用于求解方程 f(x)=1+x-x³=0 在 [1,2] 内的根，精度要求 1e-5。运行示例输入 a=1, b=2, e=1e-5，输出近似解为 1.32472。

代码逻辑：首先判断区间端点是否已满足精度，若否且 f(a)f(b)>0 则报错；否则循环计算中点 c，根据 f(a)f(c) 的符号更新区间边界，直至区间宽度小于 e，输出中点作为解。

二分法具有线性收敛速度，收敛因子为 1/2，即每次迭代误差减半。初始区间长度为 L，经过 k 次迭代后，误差不超过 L/2^k。因此达到精度 ε 所需迭代次数至少为 log₂(L/ε)。该方法虽然收敛速度较慢，但稳定可靠，无需函数导数信息。下表显示了不同迭代次数对应的误差范围：

二分法与 Newton-Raphson 法、割线法等相比，无需导数，收敛确定性高，但速度较慢。Newton 法在根附近二次收敛，但可能发散。割线法超线性收敛，但稳定性稍差。二分法常作为初值获取方法，与其他方法结合使用。

二分法广泛应用于科学计算、工程优化和计算机科学中。例如：

• 求解非线性方程：如求 x³-x-1=0 的根。
• 优化算法中寻找目标函数的极值点（利用一阶导数为零的条件）。
• 数据结构中用于有序列表的查找（二分查找）。
• 机器学习中的参数调优（如学习率搜索）。

此外，二分法也是许多复杂算法的基础模块。

二分查找（Binary Search）是二分法在有序数组搜索中的特例，时间复杂度 O(log n)，广泛应用于数据库索引、字典查找等。其原理类似：每次取中间元素对比，缩小搜索区间。

二分法以其简单、可靠、无需梯度的特点，成为数值计算和算法设计中的基石。尽管收敛速度有限，但其稳健性使其在工程实践中仍不可或缺。通过与其他快速方法结合，可在保证收敛的同时提升效率。

• 李庆扬, 王能超, 易大义. 数值分析（第5版）. 清华大学出版社, 2008.
• 冯康. 数值计算方法. 国防工业出版社, 1978.
• Burden, R. L., & Faires, J. D. Numerical Analysis (9th ed.). Brooks/Cole, 2011.
• Press, W. H., Teukolsky, S. A., Vetterling, W. T., & Flannery, B. P. Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press, 2007.
• Kincaid, D., & Cheney, W. Numerical Analysis: Mathematics of Scientific Computing (3rd ed.). Brooks/Cole, 2002.
• Stoer, J., & Bulirsch, R. Introduction to Numerical Analysis (3rd ed.). Springer, 2002.
• 张平文, 李若. 数值分析. 北京大学出版社, 2015.