69. x 的平方根 - 力扣（LeetCode）​​​​​​

解法：二分查找

思路：看示例2：

可以看到8的平方根是2.82，在2^2和3^2之间，所以可以把数组分为两部分，(具有二段性)

而2.82去掉小数部分会变为2，所以返回值在 <x 的区间右端点上。

细节

1.此题没有数组，但可以直接用两个整数来模拟。

2.这一题的范围虽然在int范围内，但是中间判断逻辑是 1^2 2^2(1*1 2*2)这样的相乘逻辑，肯定会越界，所以用long long int.

3.边界情况：0，单独判断

class Solution 
{
public:int mySqrt(int x) {if(x == 0)return 0;long long int left = 1,right = x;long long int mid = 0;while(left < right){//1.求区间右端点mid = left + (right - left + 1) /2;long long int mm = mid * mid;if(mm <= x)left = mid;elseright = mid - 1; }return left;}
};