算法：69.x的平方根

题目

链接：leetcode链接

思路分析（二分算法）

当然你可以使用暴力查找，但是二分算法的时间复杂度更好。

我们先用暴力查找找点灵感

x ：1 2 3 4 5 6 7 8
x²：1 4 9 16 25 36 49 64

我们的目的是找到一个x使得x²恰好小于target
观察x²序列，我们可以发现分成两部分，一边 <= 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;}