使用二进制搜索在C中查找数字的平方根 [英] Using binary search to find the square root of a number in C

问题描述

尝试使用二进制搜索计算数字的平方根，但是我对它的实现无法正常工作，我不确定为什么-感谢您提供任何帮助，谢谢

Trying to work out the square root of a number using binary search, however my implementation of it is not working and i'm not sure why - any help appreciated, thank you

这里是我的代码. "end"是我想平方根的数字的值

Heres my code. 'end' being the value of the number I want to be square rooted

 while(start <= end) {
   float mid = ((start + end) / 2);
   printf("\nhalving mid");

   if(mid * mid == end){
      sqrt = mid;
      printf("\nsqrt = %d", sqrt);
   }
   if(mid * mid < end){
     start = mid + 1;
     sqrt = mid; 
     printf("\nsqrt: %d", sqrt);
   }
   else{
     start = mid - 1;
   }
 }

推荐答案

除了代码中的逻辑问题外，比较浮点数也不是一个好习惯.

In addition to the logic problems in your code, it is not a good practice to compare floating point numbers.

mid * mid == end可能始终会失败，即使对于sqrt(9)也是如此，因为很难测试浮点数是否相等.

mid * mid == end will probably always fail, even for sqrt(9) because it is very difficult to test floating-point numbers for equality.

使用范围(epsil)而不是比较来查看此实现:

Look at this implementation using a range (epsil) instead of comparison:

static float my_sqrt(float num)
{
    double start = 0.0;
    double end = num;
    double sqrt = 0.0;
    double epsil = 0.000001;

    while (start <= end)
    {
        double mid = ((start + end) / 2);

        sqrt = mid;
        printf("sqrt = %f\n", sqrt);
        if (fabs(mid * mid -num) <= epsil)
        {
            break;
        }
        else if (mid * mid < num)
        {
            start = mid;
        }
        else
        {
            end = mid;
        }
    }
    return sqrt;
}

这篇关于使用二进制搜索在C中查找数字的平方根的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！