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

Question

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

实现一个函数 root 来计算一个数的第 n 次方根。该函数取一个非负数 x 和一个正整数 n，并在 0.001 的误差范围内返回 x 的第 n 个正根(即假设实根为 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;
}

这达到了左>右的条件并返回-1。

有没有一种方法可以使用二进制搜索来实现它？

Answer 1

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

使用 double 进行二分查找可能很棘手，根据您真正想要的结果，有多种方法可以做到这一点。在这种情况下，要求您在实际根的 0.001 以内给出答案。 不要求您的答案^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;
}

请注意，不可能返回“未找到”