前言： 

在前期，我们讨论了成功失败算法和黄金分割算法，那么这一期，我们来看看一种最为常见也最为简单的一维搜素方法——二分法

成功-失败算法（算法分析+python代码解释）https://blog.csdn.net/m0_61209712/article/details/133940690

黄金分割算法（算法分析+python代码解释）https://blog.csdn.net/m0_61209712/article/details/133973395

当对收敛速度要求不是很高并且函数性质较好时，我们就可以采用两分法。具体做法如下：

设函数在区间[a，b]上为具有一阶导数的单峰函数，且满足。令，如果，则最优解为。若，则令，区间被减半，重新开始。若，则令，区间被减半，重新开始，直到区间的长度小于事先给定的精度ε，或者ε为止。

算法步骤：

步骤1：给定a，b，ε0.

步骤2：计算。

步骤3：如果ε或者ε，则转步骤4。否则若，则令，转步骤2；若，则令，转步骤2。

步骤4：停止，输出

例题分析：

下面我们通过一道例题来加深一下对算法的认识。

例题：试用二分法求目标函数的最优解。给定初始区间[0，2]，收敛精度ε=0.004.

解：首先判断在给定区间内是否含有极点：

函数在该区间有极小值

第一次区间缩短计算过程：

令,又ε,开始下一次

第二次区间缩短计算过程：

令,又ε,开始下一次

第三次区间缩点计算过程：

令,又ε,开始下一次

------

第九次区间缩短计算过程：

，又ε,故

算法代码：

'''
二分法算法
2023.10.9
'''
from sympy import *
x = symbols("x")
f_x = x ** 2 + 2 * x - 10
def run(a,b,ε):
    count = 0
    # 一阶求导
    first_grad = diff(f_x, x)
    # 判断给定区间内是否存在极小点
    if first_grad.subs({x: a})*first_grad.subs({x:b}) > 0:
        print("该函数在该区间不存在极小点,该函数在该区间单调")
        if f_x.subs({x:a}) > f_x.subs({x:b}):
            print("最小值在{}处取到".format(b),"为{}".format(f_x.subs({x:b})))
        elif f_x.subs({x:a}) < f_x.subs({x:b}):
            print("最小值在{}处取到".format(a),"为{}".format(f_x.subs({x:a})))
    else:
        print("该函数在该区间存在极小点")
        while abs(b-a) > ε:
            count = count+1
            print("第{}次迭代".format(count))
            x0 = (a+b)/2
            #print(x0)
            if first_grad.subs({x: x0}) > 0:
                b = x0
            elif first_grad.subs({x: x0}) < 0:
                a = x0
            elif first_grad.subs({x: x0}) == 0:
                print("该精度下的最优解是：%f" % x0)
                print("缩短之后的区间为：[%f,%f]" % (a, b))
                break
        print("缩短之后的区间为：[%f,%f]"%(a,b))
        print("该精度下的最优解是：%f"%x0)
        return x0
run(-1,5,0.0001)

用该代码所运算的结果为：

该函数在该区间存在极小点
第1次迭代
第2次迭代
第3次迭代
第4次迭代
第5次迭代
第6次迭代
第7次迭代
第8次迭代
第9次迭代
第10次迭代
第11次迭代
第12次迭代
第13次迭代
第14次迭代
第15次迭代
第16次迭代
缩短之后的区间为：[-1.000000,-0.999908]
该精度下的最优解是：-0.999908

总结：

在成功-失败算法和黄金分割算法的迭代过程中，仅仅利用了函数值就能够找到函数在某区间上的最小值，这样做固然简单方便，计算量也小，但是如果函数的性质比较好（比如已知函数的导数），我们就可以选用更为简单或者收敛速度更快的迭代算法——二分法。

（行文中若有纰漏，希望大家指正）