Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Solution:
a * a = x, our task is to find a.
Brute-Force is O(n) time, and it will exceed time limit.
So, we can use binary search to optimize.
Tips: use "long" type in case of overflow.

public class Solution {
    public int sqrt(int x) {
        
        if(x <= 0) 
            return 0;
        if(x == 1)
            return 1;
            
        long l = 0;
        long r = x / 2;
        while(l < r){
            long mid = (l + r) / 2;
            if(mid * mid == x) 
                return (int)mid;
            else if(mid * mid > x){
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        // x may not be square number
        if(l * l > x) l -= 1;
        return (int)l;
    }
}