题目描述请实现 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<r){ int mid=l+r+1ll>>1; if(mid<=x/mid)l=mid; else r=mid-1; } return l; } };
转载于:https://www.cnblogs.com/programyang/p/11154504.html
