平方根
求平方根
http://www.nowcoder.com/questionTerminal/09fbfb16140b40499951f55113f2166c
题目描述
实现函数 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;
}