CODEWITHSUNDEEP
calgorithmmath
LC12382
LC12382

Reputation: 97

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

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

Upvotes: 4

Views: 10066

Answers (5)

Prathu Baronia
Prathu Baronia

Reputation: 125

You should replace your last line with 

end = mid -1

in the else snippet

Upvotes: 0

Ashok
Ashok

Reputation: 763

public int sqrt(int x) {
    if (x == 0)
        return 0;
    int left = 1, right = Integer.MAX_VALUE;
    while (true) {
        int mid = left + (right - left)/2;
        if (mid > x/mid) {
            right = mid - 1;
        } else {
            if (mid + 1 > x/(mid + 1))
                return mid;
            left = mid + 1;
        }
    }
}

Upvotes: -1

user1196549
user1196549

Reputation:

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.

Upvotes: 1

Lutz Lehmann
Lutz Lehmann

Reputation: 26040

Certainly the last line should be

 end = mid - 1;

conforming to the three cases

start..mid-1, mid, mid+1..end

And you should separate the number num that you want to compute the square root of and the end end of the search interval.

Of course you will also get a problem when the square root is not an integer. Then at some point it will fall inside one of the intervals (mid-1, mid) or (mid, mid+1) and thus outside of your algorithm.

Thus you need to separate the cases as

[start, mid] (mid, mid+1), [mid+1,end]

if you want to stay with integer boundaries. The middle case is

 ( mid*mid> num ) && ( (mid+1)*(mid+1) < num )

Upvotes: 0

eyalm
eyalm

Reputation: 3366

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

Upvotes: 8

Related Questions