A Binary Search Solution


  • 173
    A

    Instead of using fancy Newton's method, this plain binary search approach also works.

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

  • 0
    D
    This post is deleted!

  • 1
    D

    Can you please explain the logic behind this code?


  • 3
    A

    left/ right are the min and max values of an interval.
    each loop divide the interval by half and pick the left half or right half and continue.
    this is really the same idea as binary search.


  • 76
    Y

    The first right needn't to be MAX integer, the right at most x


  • 0
    A

    Agree, thanks.


  • -8
    U

    minor things I found, int mid = left + (right - left)/2 is the same as (right + left)/2.


  • 24
    A

    It's to prevent potential integer overflow.


  • 11
    C

    if the left and the right is very big,the (right+left) may exceed the INT_MAX,so it's better to use left+(right-left)/2 instead


  • 3

    set left = 1 and right = Integer.MAX_VALUE is not a good idea, right = mid - 1 and left = mid + 1 is also not a good idea. In order to speed up the calculation, you can write code as follow:

    int sqrt(int x)
    {
    	int bits = static_cast<int>(std::log10(static_cast<double>(x))) / 2;
        int low = static_cast<int>(std::pow(10.0, bits)), high = static_cast<int>(std::pow(10.0, bits + 1));
        while (high - low > 1)
        {
            int mid = low + (high - low) /2;
            mid > x / mid ? high = mid : low = mid;
        }
        return low;
    }
    

  • 2

    Just wondering, why bother setting low and high using std::pow, isn't it easy to just set it to 1 and x, as the result will be within it?

    var mySqrt = function(x) {
        var low = 1;
        var high = x;
        while (low + 1 < high) {
            var mid = low + ((high - low) >> 1);
            mid * mid > x ? high = mid : low = mid;
        }
        return low;
    };

  • 3
    J

    Would you like to explain the difference between "mid > x / mid" and "mid * mid > x"? Thx!


  • 3
    A

    If mid > x/mid, then mid^2 > x; we know mid is bigger than the root of x, so we should try something smaller than mid.
    Similar for mid < x/mid.


  • 18
    K

    I think he was confused about why it is not equivalent to midmid > x (which mathematically it is...). The key is that midmid will overflow the integer if mid is large enough. Therefore it is better to do mid> x/mid, as that will definitely NOT overflow as long as mid is a valid positive int.


  • 0
    H

    You may add
    if ( x === 0 ) return 0;
    at the beginning. Thanks.


  • 0
    C

    That is really explain everything. Thanks kiratomatoes!


  • 130

    An accepted concise version:

    • The sequence 1, 2, ... , n has no duplication.
    • Near the very end, closest step, before while loop, left = mid = right.
    • In while, If mid < sqrt(x), left = mid + 1 executed, right pointer is not moving, and right is the answer.
    • If while, If mid > sqrt(x), right = mid - 1 executed, right pointer shifts left 1, closest to sqrt(x), right is also the answer.
    public int mySqrt(int x) {
        int left = 1, right = x;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid == x / mid) {
                return mid;
            } else if (mid < x / mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

  • 0
    T

    This solution is really awesome and easy to understand! Thanks a lot!


  • 1
    K

    actually they are not the same. (right + left)/2 may end up with overflow.


  • 1
    J

    yes,but why cannot it be like "if ((mid + 1)*(mid + 1) > x)"


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.