题解 | #求平方根#

class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    int sqrt(int x) {
        int l = 1, r = x / 2;
        while (l <= r) {
            int m = l + (r - l) / 2;
            long long tar = (long long)m * m;
            if (tar < x) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return l * l == x? l: r;
    }
};

思路：二分查找。

因为是向下取整，所以查找完后要先判断l是否正好是x的平方根，是则返回l，否则r是x平方根向下取整。