题目链接：Sqrt(x)
Implement int sqrt(int x).
Compute and return the square root of x.
这道题的要求是实现int sqrt(int x)，即计算x的平方根。
考虑二分，即先令l和r分别为1和x/2+1（x的平方根一定小于等于x/2+1），然后m等于(l+r)/2，不断比较m*m和x的大小。
由于m*m的时候，可能溢出，因此可以用除法代替乘法，或者采用long long类型。
时间复杂度：O(logn)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution{
public:
int sqrt(int x)
{
if(x == 0)
return 0;
int l = 1, r = x / 2 + 1;
while(l <= r)
{
int m = (l + r) / 2;
if(m <= x / m && m + 1 > x / (m + 1))
return m;
if(m > x / m)
r = m - 1;
else if(m < x / m)
l = m + 1;
}
return l;
}
};