Using binary search to find the square root of a number in C

Question

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

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;
   }
 }

Answer 1

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

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

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;
}

Answer 2

I am not fixingyour code, just explaining how I would write it.

Use an invariant that expresses the bracketing of the solution:

low² <= N < high²

Then taking an intermediate value mid, the test

mid² <= N

allows to choose among

low² <= N < mid² and mid² <= N < high²

and narrow down the search interval.

The iterations can stop when the search interval is a small as the floating-point representation allows (i.e. 23 bits for single precision). You can stop when low == high.

To establish the invariant,

low= 0, high= N

can do, provided that 0 <= N < N². This doesn't work when N <= 1. A quick and dirty workaround is to set high= 1.

low= 0
if N >= 1:
    high= N
else:
    high= 1

while low < high:
    mid= 0.5 * (low + high)
    if mid * mid <= N:
        high= mid
    else:
        low= mid

---

IMO, testing for equality mid² == N, then inequality mid² < N is counter-productive. You may be tempted to think that early termination when N is a perfect square allows to shorten the execution time. But in reality, most of the input numbers are not perfect squares and you will be performing two tests instead of one, making the program slower on average.