c - 使用二进制搜索和递归查找函数的根

Question

有人可以解释一下，为什么我们需要最大值和最小值之间的差小于误差(三次方程的根)？其背后的逻辑是什么？为什么我们需要返回 min？

代码如下:

#include <stdio.h>
#include <stdlib.h>

double func(double x)
{
    return x * x * x  + 2 * x * x - 2;
}

double zeroFinder(double min, double max, double error)
{

    if ((max - min) < error)
    {
        return min;
    }
    double x = (max + min) / 2;

    if (func(x) < 0)
    {
        min = x;
    }
    else
    {
        max = x;
    }

    return zeroFinder(min, max, error);
}

int main(void)
{
     zeroFinder(0.0, 1.0, 0.01);
     zeroFinder(0.0, 1.0, 0.001);  
     zeroFinder(0.0, 1.0, 0.000001);    
     zeroFinder(0.0, 1.0, 0.0000000001);

     return 0;
} 

Answer 1

该算法正在实现称为 Bisection Method 的东西.这个想法是从一个间隔开始(在您的情况下由 max 和 min 分隔)，评估中点的值，然后适当缩短间隔。

这与实际行上的二分查找完全一样。然而，由于我们试图找到一个实数值，函数可能不会在有限次数的迭代中终止于实数值(例如，当答案是 sqrt(2) 时)。此外，由于该方法计算浮点变量，通常您不会获得准确的值。然而，迭代算法应该终止于一组有限的迭代。因此，当间隔变得足够小时(即当 abs(max - min) < <some error value> 时，我们可以让函数终止。这意味着获得的答案在正确答案的 some error value 范围内。

正如@Elyasin 在评论中提到的，代码可以返回 max , min或介于两者之间的任何值作为答案。可能对开闭区间有一些考虑，所以返回(max + min) / 2.0也是一个安全的选择。