Sqrt(x)

Problem

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.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Constraints:

0 <= x <= 2³¹ - 1

Solution

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let lo = 0;
    let hi = x;

    while (lo <= hi) {
        const mid = Math.ceil((lo + hi) / 2);
        if (mid ** 2 > x) { // mid is too large
            hi = mid - 1;
        } else if ((mid + 1) ** 2 > x) { // mid == floor(sqrt(x))
            return mid;
        } else { // mid is too small
            lo = mid + 1;
        }
    }
};

We will implement a binary search solution. More specifically, we can approximate the value of sqrt(x) rounded down. Observe that the result squared should be less than or equal to x, and the result plus 1 squared should be greater than x. In other words, mid² <= x < (mid + 1)² implies mid <= sqrt(x) < mid + 1 implies mid == floor(sqrt(x)).

Problem​

Solution​

Problem

Solution