题解 | #求平方根#

思路分析：

x 的平方根不会超过 x / 2，特殊情况可以解下面的方程：

解得：。因此，需要对 x = 0, 1, 2, 3 做单独的讨论。

参考代码：

public class Solution {

    public int mysqrt(int x) {
        // 注意：特殊用例判断
        if (x == 0) {
            return 0;
        }
        if (x < 4) {
            return 1;
        }

        int left = 0;
        int right = x / 2;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (mid > x / mid) {
                // 下一轮搜索的区间是 [left..mid - 1]
                right = mid - 1;
            } else {
                // 下一轮搜索的区间是 [mid..right]
                left = mid;
            }
        }
        return left;
    }
}