原题网址：http://www.lintcode.com/zh-cn/problem/sqrtx/
实现 int sqrt(int x) 函数，计算并返回 x 的平方根。
您在真实的面试中是否遇到过这个题？
Yes
样例
sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(10) = 3
挑战
O(log(x))
标签
#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <algorithm>
using namespace std; int sqrt(int x)
{
if (x<)
{
return -;
} long long low=,high=x,mid=(low+high)/; //为何用int会出错？;
while (low<=high) //mid*mid有可能超出int范围被截断，小于x，若(mid+1)*(mid+1)被截断后仍小于x，返回错误结果;
{
if (mid*mid==x)
{
return mid;
}
else if (mid*mid>x)
{
high=mid-;
}
else
{
if ((mid+)*(mid+)>x)
{
return mid;
}
else
low=mid+;
}
mid=(low+high)/;
} }
参考：
1 https://blog.csdn.net/gao1440156051/article/details/49766733
2 http://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html