题解 | #求平方根#

解题思想

整数二分
这里需要注意：有可能实际的平方根在mid和mid-1中间，因此需要及时return mid-1，以防错过解的区间。其他地方均按照整数二分方法的模板去做即可。

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

    int mysqrt(int x) {
        // write code here
        if(x==0)    return 0;
        int res = divide(1, x, x);
        return res;
    }
};