时间戳

首页 > 解决方案 > 使用递归的函数的二进制搜索根

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

问题描述

我正在尝试编写一个二进制搜索函数来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)。

谢谢您的帮助。

标签： pythonpython-3.xrecursionbinary-search

解决方案

您所看到的是您的函数仅适用于递增函数，这对于x**2 - 2between0和是正确的3，但不适用于递减函数，这对于您的函数 between -3and是正确的0。

有几种方法可以修复您的功能。一种方法是交换start和endif的值fun(start) > fun(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.'

推荐阅读