LeetCode 69. Sqrt(x)

Problem

LeetCode 69. Sqrt(x)

1. 题目简述

给出一个数字x，计算其开方，向下取整。

2. 算法思路

最经典的几道题目之一，有很多坑。

第一，注意不要用 mid * mid，很容易越界，不好办。其次，注意问题的本质，究竟是要求左边界还是右边界！！！也就是check成立时，我们希望继续去找左侧还是右侧。

这里，我们希望找的是右边界，也就是要找到一个“最大”的y，使得y^2<=x。

class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x;
        
        while (l < r) {
            // 这里应该是求右边界！！！找到一个数y，使得y^2 <= x
            int mid = (l + r + 1) / 2;
            if (mid <= x / mid) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        
        return r;
    }
}