使用递归的函数的二进制搜索根

Question

我正在尝试编写一个二进制搜索函数来查找区间 [,]:

中函数 fun 的根

这是我所拥有的接近但缺少标记的内容：

def binarySearchIter(fun, start, end,  eps=1e-10):
    '''
    fun: funtion to fund the root
    start, end: the starting and ending of the interval
    eps: the machine-precision, should be a very small number like 1e-10

    return the root of fun between the interval [start, end]
    '''

    root = (start + end)/2
    print(root)

    answer=fun(root)

    if abs(answer) <= eps:
        print(root)
        return root
    elif answer - eps > 0:
        binarySearchIter(fun, start, root, eps=1e-10)
    else:
        binarySearchIter(fun, root, end,  eps=1e-10)

这是我用来测试的函数：

def f(x):
return x ** 2 - 2

当我运行: binarySearchIter(f, -3, 0, eps = 1e-10) 我期待一个答案: -1.4142135623842478, 然而, root 收敛到 -3 直到它超时.

当我运行 binarySearchIter(f, 0, 3, eps = 1e-10) 我得到 1.4142135623842478 的正确答案。

我显然遗漏了一些使函数中断的东西，具体取决于它是 (-3, 0) 还是 (3,0)。

感谢您的帮助。

Answer 1

您看到的是您的函数仅适用于递增函数，对于 0 和 3 之间的 x**2 - 2 是正确的，但不适用于递减函数，这对于 -3 和 0.

之间的函数是正确的

有多种方法可以修复您的函数。一种方法是如果 fun(start) > fun(end) 交换 start 和 end 的值。换句话说，将行 root = (start + end)/2 更改为三行

if fun(start) > fun(end):
    start, end = end, start
root = (start + end)/2

这确实会减慢您的日常活动，因此有更好的方法来完成您的日常活动。特别是，使用迭代而不是递归。 Python 与迭代相比，递归的速度相当慢。

但是，您的功能并不健壮。您应该首先检查 fun(start) 和 fun(end) 是否有不同的符号。然后，您的例程将继续重新定义 start 和 end，以便它们的图像继续具有相反的符号。如果符号相同，那么你的函数在那个区间内可能没有根，你的例程肯定没有好的方法来决定继续搜索哪一半区间。一种方法是在我已经插入的行之前添加这两行：

if fun(start) * fun(end) > 0:
    raise 'Endpoints in binarySearchIter should yield opposite signs.'

使用递归的函数的二进制搜索根

Binary search root of function using recursion

python

recursion

binary-search

python-3.x