二进制搜索以找到数字的 n 次根

Question

我尝试使用二进制搜索实现一个函数来解决以下问题：

实现一个函数 root 来计算一个数的 n 次方根。该函数取一个非负数 x 和一个正整数 n，returns x 的第 n 个正根，误差在 0.001 以内（即假设实根为 y，则误差为：|y- root(x,n)| 且必须满足 |y-root(x,n)| < 0.001）。关键是在不使用STL函数的情况下找到根。

我的代码：

double binarysearch(double left,double right, double x, int n){
 while(left<right){
  double mid = left + (right-left)/2;
  double answer = pow(mid,n);
   if(fabs(answer - x ) <= DELTA)
    return mid;
  else if(answer > x )
      right = mid - DELTA;
  else 
     left = mid + DELTA;
 }
  return -1;
}

这就达到了左>右，returns-1的情况。

有没有办法使用二进制搜索来实现这个？

Answer 1

您的函数中断，因为 (mid-DELTA)^n 和 mid^n 之间的差异通常大于 三角洲.

使用双精度进行二分查找可能会很棘手，根据您真正想要的结果，有多种方法可以做到这一点。在这种情况下，要求您在实际根的 0.001 以内给出答案。不要求您的 answer^n 在 x 的 0.001 以内。

建议这样实施：

double binarysearch(double x, int n)
{
    double lo = 0.0;
    double hi = x;
    while(hi-lo >= 0.0019)
    {
        double test = lo+(hi-lo)*0.5;
        if (test == low || test == hi)
        {
           //I couldn't bear to leave this out.  Sometimes there are no
           //double values between lo and hi.  This will be pretty much
           //as close as we can get.  Break here to avoid an infinite loop
           break;
        }
        if (pow(test,n) < x)
        {
            lo = test;
        }
        else
        {
            hi = test;
        }
    }
    //cut the final range in half.  It's less than
    //0.0019 in size, so every number in the range, which includes
    //the root, is less than 0.001 away from this
    return lo+(hi-lo)*0.5;
}

注意不可能 return "not found"

二进制搜索以找到数字的 n 次根

Binary search to find nth root of a number

algorithm

binary-search

square-root