LC69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

We use binary search between [0,n]. But the return strategy change; Instead of mid== target, we will return if mid^2 <= x and (mid + 1)^2 > x: this means sqrt(x) is between mid^2 and (mid + 1)^2.

    int mySqrt(int x) {
        int upper = x;
        int lower = 0;
        long long mid = 0;
        while(upper >= lower){
            mid = lower + int((upper - lower) / 2);

            if ((mid * mid) <= x and (mid + 1) * (mid + 1) > x){
                return mid;
            }
            else if(mid * mid > x){
                upper = mid - 1;
            }
            else if ( mid *mid < x)
                lower = mid + 1;
        }

        return -1;
    }

A note on binary search

When we set new high and new low, remember to exclude the middle, because the fact we skipped the first if statement means that middle is definitely not a candidate.

high = mid - 1
low = mid + 1

Math

https://en.wikipedia.org/wiki/Integer_square_root#Using_only_integer_division

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax