Implement floored square root using binary search

Question

Okay, so I've been working on this for some time now and I know that my logic is correct, however, I can't seem to produce the correct floored square root of a positive number.

    public int mySqrt(int x) {
        if(x < 2) return x;
    
        double lowerBound = 0.0, upperBound = x, midPoint = 0.0;
        while(lowerBound <= upperBound) {

            midPoint = lowerBound + (upperBound - lowerBound) / 2;
            double square = Math.pow(midPoint, 2);

            if(Double.compare(square, x) < 0) lowerBound = midPoint + 1;
            else if(Double.compare(square, x) > 0) upperBound = midPoint - 1;
            else return (int) midPoint;
        }

        return (int) midPoint;
    }

A test case I fail, for example, is for x = 2: it should return 1 but I return 2. which doesn't make sense because I clearly take a midPoint first. Is the logic to go left or right incorrect?

Answer 1

You shouldn't be using any double math for this. You have to do a lot more iterations to get an accurate double value, and then you just throw it away. You should use an integer solution like this:

int mySqrt(int x) {
    if (x<2) {
        return x;
    }
    int minval=1, maxval=x/2;

    while(minval < maxval) {
        // rounding up here means we never choose minval
        int test = minval + (maxval - minval + 1)/2;
        // testing this way avoids a multiply that could overflow
        if (x/test < test) {
            //too high
            maxval = test-1;
        } else {
            //not too high
            minval = test;
        }
    }
    return minval;
}