Why is this code for sqrt(x) coding challenge working?

user_19087378 0
Viewed 55

I am currently studying binary search so I solved this coding challenge:

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned. from leetcode https://leetcode.com/problems/sqrtx/

I used the following code, but I don't understand why in some cases I have to return sqrt-1, and in some other cases just sqrt.

var mySqrt = function(x) {
    let min = 0;
    let max = x;
    let sqrt;
    while(min<=max){
        sqrt = Math.floor((min+max)/2);
        if(sqrt*sqrt == x ){
            return Math.floor(sqrt);
        } else if(sqrt*sqrt < x){
            min = sqrt + 1;
        } else max = sqrt - 1;
    }
  return sqrt*sqrt > x ? sqrt-1: sqrt;
};

binary-search arrays javascript
1 Answers

On each iteration, it gets a bit closer to the result. The min number will always get higher, and the max number will always get lower, and by using those two numbers, a sqrt number is also calculated. There are 4 possibilities:

  • If min matches max, there is nowhere further to narrow; you're right at the edge of the square root. So the code does return sqrt*sqrt > x ? sqrt-1: sqrt; - if the current sqrt produces a value too high, what's returned is sqrt - 1, else it returns sqrt. One of those values is necessarily the desired result.
  • If the calculated sqrt is the true square root (sqrt*sqrt == x), then it can be returned immediately.
  • if(sqrt*sqrt < x) indicates that the square root is too small, and so the minimum value should be raised (hence min = sqrt + 1)
  • The only other possibility is that the square root is too large, and so the maximum value is decremented (hence max = sqrt - 1)

Eventually you'll come to a point where either you find an exact match, or you'll be on the edge between deciding on sqrt and sqrt - 1, and can return the appropriate value.

user_95152070
Related