算法019—— x的平方根

力扣—— x 的平方根（点击跳转）

当 x = 17 时，返回 4，我们发现此时 4 的平方根小于 x
当 x = 36 时，返回 6，我们发现此时 6 的平方根等于 x

根据这个我们可以找到题中的 二段性

我们定义一个变量 ret 表示最终结果，最终结果会将整个数组划分成两个区域
因此我们可以使用二分查找来解决问题

mid 的平方在哪个区间内，有两种情况

1. mid * mid <= x，此时应该在右边寻找，移动 left ,让 left = mid，不能等于 mid+1,因为 mid 的位置可能是 ret ，如果等于 mid + 1，会错过
   
2. mid * mid> x,此时应该在左边寻找，让 right = mid - 1
   
   注意：

• 当 x < 1 时，我们直接返回 0 即可
• 由于 mid * mid 数据太大，有可能溢出，所以它的类型我们定义为 long，所以 left 与 right 的类型也定义为 long，最后返回的时候要注意强转

代码如下

class Solution {public int mySqrt(int x) {if(x < 1) return 0;long left = 1;long right = x;while(left < right){long mid = left + (right - left + 1) / 2;if(mid * mid <= x){left = mid;}else{right = mid - 1;}}return (int)left;}
}

easy