CODEWITHSUNDEEP
javaalgorithmbinary-search
Mutating Algorithm
Mutating Algorithm

Reputation: 2758

Implement floored square root using binary search

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?

Upvotes: 3

Views: 142

Answers (3)

Unmitigated
Unmitigated

Reputation: 89422

Since you are performing binary search on a double value, you should set a tolerance, and stop looping once the difference between high and low drops below that tolerance (a standard tolerance would usually be 1e-6). You also should set low = mid or high = mid instead of adding or subtracting one, as you are not binary searching over int values. See the below code in action here.

private static final double TOLERANCE = 1e-10;
public int mySqrt(int x) {
    if (x < 2)
        return x;
    double lowerBound = 0.0, upperBound = x, midPoint = 0.0;
    while (upperBound - lowerBound >= TOLERANCE) {
        midPoint = lowerBound + (upperBound - lowerBound) / 2;
        double square = Math.pow(midPoint, 2);
        if (Double.compare(square, x) < 0)
            lowerBound = midPoint;
        else if (Double.compare(square, x) > 0)
            upperBound = midPoint;
        else
            return (int) midPoint;
    }
    return (int) midPoint;
}

If you never anticipate needing more precision, you can just binary search using ints. See the below code in action here.

public int mySqrt(int x) {
    if (x < 2)
        return x;
    int low = 0, high = x;
    while (low < high - 1) {
        final int mid = low + high >>> 1;
        if (mid <= x / mid) {
            low = mid;
        } else {
            high = mid;
        }
    }
    return low;
}

Upvotes: 4

pjs
pjs

Reputation: 19855

Since the input is int and the result is int, this shouldn't involve floating point arithmetic at all.

public static int mySqrt(int i) {
    if (i < 2)
        return i;
    int lower = 0, upper = i;
    do {
        int guess = lower + (upper - lower) / 2;
        if(guess <= i / guess) {
            lower = guess;
        } else {
            upper = guess;
        }
    } while ((upper - lower) > 1);
    return lower;
}

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59303

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

Upvotes: 2

Related Questions