使用 nextafter() 进行二分查找

Question

我输入了一个双 n 并试图通过二进制搜索找到根。 epsilon 的中断条件有点长，我正在考虑使用 nextafter() 来高精度计算结果。

double lower = 1, upper = n, mid, midSquared;
while (nextafter(lower,upper) < upper) {
    mid = (l + u)/2.;
    midSquared = mid * mid;
    if (midSquared < n) lower = mid;
    else upper = mid;
}

我能保证我的循环会以这种方式终止吗？这实际上是关于中期。当有可显示的值时，mid 会取下限和上限之间的值吗？在我看来，这是一种不错的方法，因为它与排序列表上的索引比较二进制搜索相匹配。（下标 + 1 < 上标）

Answer 1

将 lower 初始化为 0 并将 upper 初始化为最小值 1 将允许您的代码找到小于 1 的值的平方根。

如果您不对 n 进行范围验证，我将对 nextafter 的 return 值进行错误检查。检查 NaN 和 HUGE_VAL.

double lower = 0;
double upper = (n < 1) ? 1 : n;
double next = nextafter(lower, upper);

while (!isnan(next) && (next < upper) && (next != HUGE_VAL))
{
    double mid = (lower + upper) / 2.;
    double midSquared = mid * mid;
    if (midSquared < n)
    {
        lower = mid;
    }
    else
    {
        upper = mid;
    }
    next = nextafter(lower, upper);
}

如果你真的想确定，你也可以在循环上放一个计数器，如果循环太多就中止。

int count = 0;
while (!isnan(next) && (next < upper) && (next != HUGE_VAL) && (count < 1000))
{
    count++;
    double mid = (lower + upper) / 2.;
    ...

使用 nextafter() 进行二分查找

Binary Search with nextafter()

c++

binary-search