leetcode367 判断该数是否是完全平方数

题目地址 367. 有效的完全平方数。题目要求不能用库函数来直接开平方，本意是希望用二分法来解决该问题。

1. 完全平方数的解决方案 #

两种方式：

1. 直接检索：从 1 开始匹配，挨个儿匹配 num，直到能匹配上（返回 true），或超过 num（返回 false）。时间复杂度为 O(n)；
2. 二分查找：取中间数来匹配 num，匹配上就直接返回，否则根据大小来决定取左边或者右边；

无论使用哪种方式，都应该注意类型范围和精度这两个问题。

题目中限制了 num 的范围在[1, 2^31-1]，若我们选择了 int 类型，并且用乘方结果来跟 num 进行匹配时，无论是直接检索还是二分查找，都会极大概率出现超过类型范围的问题。这里应该选择long long类型。

同时，取中间值时，不要直接(left+right)/2，这也会超出 int 范围的，应该使用 left + 偏移量的方法：

mid = left + (right - left) / 2;

我们换个角度，为避免数字超过类型范围，用 num 来除以这个数 mid，再判断商是否等于 mid。但在 C/C++中，会舍弃小数，导致判断失败，如 10000 和 10001 两个数字：

int result0, result1, mid = 100;

result0 = 10000 / 100;
result1 = 10001 / 100;

result0 == mid; // 正确，expect true, receive true
result1 == mid; // 错误, expect false, receive true

这里最好再用取余判断下是否可以整除，最终的代码：

class Solution {
public:
    bool isPerfectSquare(int num) {
        int left, right, mid;
        int square;

        left = 1;
        right = num;

        while (left <= right) {
            mid = left + (right - left) / 2;
            square = num / mid;

            if (square == mid) {
                return num % mid == 0;
            }
            if (square > mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 没找到
        return false;
    }
};

2. 平方根 #

这里还有个上面平方数的姊妹篇：69. x 的平方根 ，即求 x 的平方根的整数位置。

跟上面的思路一样，要考虑取中间数的方式和用于相除来代替相乘，避免超出整型数字范围。

最终实现的代码如下：

class Solution {
public:
    int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        int left, right, mid, result;

        left = 1;
        right = x;

        while (left <= right) {
            mid = left + ((right - left) >> 1);
            result = x / mid; // 已自动取整

            if (result == mid) {
                return mid;
            }
            if (result > mid) {
                // result大，说明mid做为除数偏小，应当向右移动
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
};

关键点在于 x / mid在强制类型的语言中会自动取整，因此若mid == x / mid时，就说明 mid 是 x 的平方根的整数部分。

如数字 4 的平方根正好是 2 ；而 5/2==2，因此 2 就是 5 的平方根的整数部分；数字 6 则是在循环里找不到对应的数字的，会在最后返回 right 指向的值。