/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    // base case
    if (x === 1) return 1;
    let left = 0;
    let right = x;
    // start binary search
    while (left <= right) {
        let mid = Math.floor( (right + left) / 2);
        const LB = mid * mid;
        const UB = (mid + 1) * (mid + 1)
        if (LB <= x && x < UB) {
            return mid;
        } else if (x < LB) {
            right = mid;
        } else {
            left = mid;
        }
        
    }
};