1、前言

2、思路

使用二分查找的思路，查找 [0, x] 中 mid * mid <= x 的数，如果是的话，那么说明平方根藏在这个区间，先把 mid 赋值给 res 暂存下来；否则的话，right = mid - 1，缩小范围。

3、代码

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

        return res;
    }
}