平方根

题目描述
实现函数 int sqrt(int x).
计算并返回x的平方根（向下取整）

解法

 //解法：二分查找
    //时间：O（logx） 空间O（1）
    int sqrt(int x) {
        if (x <= 0) return 0;
        int l = 1, r = x;
        while (l < r) {
            long mid = (l + r) / 2;
            if (mid * mid <= x && (mid + 1) * (mid + 1) > x) {
                return mid;
            } else if(mid * mid > x) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return l;
    }