题目如下：
Implement int sqrt(int x).
Compute and return the square root of x.
分析如下：
(1)借助一个小结论，任何一个数的square都在大于等于1，小于x/2+1。很容易反证。
(2)第一次提交，发现溢出了。因为不是low, hight, mid用的类型是int，所以mid*mid可能会溢出。所以应该把数据类型设为long long。
(3)本质思想还是二分查找。
我的代码：
class Solution {
public:
int sqrt(int x) {
long long low=1;
long long high=x/2+1;
long long mid=0;
if(x==1)
return 1;
if(x<=0)
return 0;
while(low<=high){ //这里是low<=high而不是low<high，理由是，当low=high时，可能还没找到正确值，需要在进入循环体更新一次。可用sqrt(5)来验证。
mid=low+(high-low)/2;
if(mid*mid>x)
high=mid-1;
else if(mid*mid<x)
low=mid+1;
else
return mid;
}
return (low+high)/2;//注意这里是返回新的mid，也就是(low+high)/2，而不是旧的mid。如果写return mid,就将返回旧的mid，有错。
}
};