二进制搜索以找到一个数字的第n个根

Question

我尝试使用二进制搜索实现一个函数来求解以下内容：

实现一个函数root，该函数root可以计算一个数字的n'th根。该函数采用非负数x和一个正整数n，并在0.001的误差中返回x的正n根(即假设真实根为y，则误差为：| y-root(x，x，x，n(|必须满足| y-root(x，n(|＆lt; 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 。

二进制搜索带有双打可能很棘手，并且有多种方法可以取决于您真正想要的结果。在这种情况下，要求您在实际根的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;
}

请注意，没有可能返回"未找到"