Sqrt(x)

class Solution:
    def mySqrt(self, x: int) -> int:
        lo, hi = 0, x
        while lo <= hi:
            mid = (lo + hi) // 2
            if mid * mid <= x < (mid+1)*(mid+1):
                return mid
            elif mid * mid > x:
                hi = mid - 1
            else:
                lo = mid + 1
        return 0

class Solution {
public:
    int mySqrt(int x) {
        long lo = 0, hi = x;
        while (lo <= hi) {
            long mid = (lo+hi)/2;
            if (mid*mid == x) return mid;
            else if (mid*mid < x) lo = mid+1;
            else hi = mid-1;
        }
        return hi;
    }
};

function mySqrt(x: number): number {
    let lo = 0, hi = x;
    while (lo <= hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (mid * mid === x) return mid;
        else if (mid * mid < x) lo = mid + 1;
        else hi = mid - 1;
    }
    return hi;
}