[leetcode] sqrt(int) | 求一个正整数的平方根

Posted by: lexigrey on: October 6, 2013

• In: leetcode
• Leave a Comment

这题真是做了挺久，尼玛还是二分法不熟悉。。怎么终止还是想了很久。

二分法永远是(p, mid – 1)和(mid + 1, q)， 不要想什么(p, mid)之类的，那样范围永远没法缩小，最后肯定死循环。

二分的模板终止条件永远是p > q，不要去想p == q + 1, p == q这些，这些都可以经过下一次recurse再分解成p > q的形式。

最后p > q说明没找到，比如foo(5, 4)，即那么x应该是在4，5之间，这个时候p的值是5，q的值是4，说明小的那个是q,大的那个是p。所以二分法找x应该在的index那题返回p（返回较大的），这题应该返回q（返回较小的）。别去考虑p==q之类的的情况，那种再走一遍就会又形成p > q。若是找到了，更会在mid==x这个catch里直接接住，不用在终止条件处考虑。

还有一个要注意的地方：代码中间有mid * mid这种式子，这个就很可能overflow，所以要在出现这个之前接住overflow的情况。因为整数的乘法可能导致溢出，而溢出的监测和整数加法直接判断是否小于0是不同的（整数加法溢出时和会<0因为第一位bit被从0顶到1了），因为整数的乘法有可能多次溢出，当奇书次溢出时是负数，当偶数次溢出时时整数。网上看的巧妙的解决办法是干脆不要乘，而是用x/mid和mid比较。

public int sqrt(int x) {
    return sqrt(x, 1, x);
}
private int sqrt(int x, int p, int q) {
    if (p > q)
        return q;
    int mid = (p + q) / 2;
    if (x / mid == mid)
        return mid;
    else if (x / mid < mid )
        return sqrt(x, p, mid - 1);
    else
        return sqrt(x, mid + 1, q);
}

Tags: binarySearch, math, overflow