Description:
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.
Solution:
Time Complexity : O(log(n))
Space Complexity: O(1)
// Binary search approach
var mySqrt = function(x) {
let left = 1;
let right = x;
// The square root of 0 or 1 is itself
if(x < 2) return x;
// Use binary search to find the square root or the whole number closest to the square root
while(left < right) {
// Find the mid point between left and right
const mid = Math.floor((left + right) / 2)
// Return the mid point if this is the square root
if(mid*mid === x) return mid
// If mid squared is greater than x then the answer must be on the left half of mid
else if(mid*mid >x) right = mid
// If mid squred is less than x then the answer must be on the right half of mid
else left = mid+1
}
return left - 1
};
Top comments (3)
Can anyone explain this code. I know binary search but didn't get this point -
if(mid*mid === x) return mid
// If mid squared is greater than x then the answer must be on the left half of mid
else if(mid*mid >x) right = mid
// If mid squred is less than x then the answer must be on the right half of mid
else left = mid+1
}
return left - 1
the task says, we need
Input: x = 4 // input
Output: 2 // we have to return
if the mid * mid ( target ) is bigger we're going left side of the binary search ( in the case with numbers, not arrays, we're doing like this, if mid before was 4 , it is our input in first iteration, new value will be 2;
says, we going to the right side of the binary search, and 2 + 1 = 3 and we are going to search again through while
thanks for reply