求平方根

题解

class Solution {
public:
    int mySqrt(int x) {
		    // 注意边界条件， 0 <= x <= 231 - 1
        if (x == 0) return 0;

        // 暴力方法:搜索 [1, x/2 + 1]
        // x==1时,边界为 [1,1], 目标值是1
        // x==2时,边界为 [1,2]
        // x==3时,边界为 [1,2]
        // x==4时,边界为 [1,3], 目标值是2
        int l = 1, r = x/2 + 1, ans = 1;
        while(l < r) {
            int mid = l + (r-l)/2;
            if ((long long)mid*mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return ans;
    }
};