69. Sqrt(x)

Implementint sqrt(int x).

Compute and return the square root of x.

思路：二分查找。关键是判断m<x/m而不是x>m*m。后者会blow up

public class Solution {
    public int mySqrt(int x) {
        if (x<=0) return 0;
        int l = 1;
        int r = x;
        while (l<=r){
            int m = (l+r)/2;
            if (m<=x/m&&x/(m+1)<(m+1)){
                return m;
            }else if (x/m<m){
                r = m-1;
            }else {
                l = m+1;
            }
        }
        return 0;
    }
}