题目描述

请实现 int sqrt(int x)。

请计算并返回 xx 的正平方根，保证 xx 是一个非负整数。

注意返回类型是整数，所以我们只返回正平方根的整数部分。

样例1

输入：4

输出：2

样例2

输入：8

输出：2

解释：8的正平方根是 2.82842...，它的整数部分是2.

算法：二分

直接套模板二分即可，注意模板的选取(这里要选小于等于目标数的最大值，所以选第二个)

class Solution {public:    int mySqrt(int x) {        int l=0,r=x;        while(l
     
      >1;            if(mid<=x/mid)l=mid;            else r=mid-1;        }        return l;    }};