算法：69.x的平方根
题目
链接：leetcode链接
思路分析（二分算法）
当然你可以使用暴力查找，但是二分算法的时间复杂度更好。
我们先用暴力查找找点灵感
x ：1 2 3 4 5 6 7 8
x2：1 4 9 16 25 36 49 64
我们的目的是找到一个x使得x2恰好小于target
观察x2序列，我们可以发现分成两部分，一边 <= target，另一边大于 target,
由此，我们就发现了二段性，于是理所当然使用二分算法。
一些细节问题
1、这里使用的是寻找右边界的二分算法，left < right , mid = left + (right - left + 1) / 2;
2、target的范围是int，但mid * mid可能超出int的范围，需要把mid设置成long long类型
3、right - left + 1，因为这里出现了 + 1,所以可能超出int的范围，所以left就不从0开始，从1开始即可，对0进行特判即可。
代码
int mySqrt(int x) {
if(x == 0)
return 0;
int left = 1,right = x -1;
while(left < right)
{
long long mid = left + (right - left + 1) / 2;
if(mid * mid <= x) left = mid;
else right = mid - 1;
}
return left;
}