Sqrt(x) — Right Boundary Binary Search

# Python
def mySqrt(x):
    lo, hi = 0, x
    while lo < hi:
        mid = lo + (hi-lo+1)//2  # upper mid
        if mid*mid <= x: lo = mid   # could be answer
        else: hi = mid-1
    return lo

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

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