有效的完全平方数 图解题解

判断 num 是不是完全平方数，到底在找什么数

给一个正整数 num，问有没有整数 x 满足 x×x=num，有就返回 true、没有返回 false，而且不许调用 sqrt 开方。题面 num=144 返回 true，12×12 正好是 144；num=14 返回 false，3²=9、4²=16，中间没有哪个整数平方等于 14。

从 1 挨个试到 num，会白算掉多长一截

逐个试值：让 x 从 1 数到 num，每个都平方看等不等于 num，等于就 true、否则 false。可 num 若接近 20 亿，最坏得试上十几亿次，时间 O(n)（n 是 num 的大小）。sqrt 又被禁用，挨个试根本走不动。

平方只增不减，半截候选可以整段跳过

关键在平方本身有序：x 越大，x×x 越大，绝不回头。把候选 x 从 1 排到 num，拿正中间的候选 mid 平方后和 num 比：mid×mid 比 num 小，mid 和它左边所有候选都够不着，左半连 mid 一起扔；比 num 大，右半全超了、一起扔。一比就砍掉一半候选，这就是二分查找，每轮砍半往剩下半边找。

取中点比完平方，该往哪半收、循环停在哪

用两个指针 l、r 圈住还没排除的候选，起点 l=1、r=num，两端都算数，是闭区间 [l,r]。每轮取中点 mid=(l+r)//2，算 sq=mid×mid 和 num 比：相等就返回 true；sq 偏小，x 在右边，l 抬到 mid+1；sq 偏大，x 在左边，r 压到 mid-1。收缩都要跨过 mid，留着已验过的它就缩不动。循环写 while l<=r，好让 l、r 撞到同一格时再比一次；l 越过 r 还没相等就返回 false。

num=144 逐轮列出 mid 和它的平方

起点 l=1、r=144。第一轮 mid=72，72×72=5184>144 偏大，r 压到 71。第二轮 mid=36，36×36=1296>144，r 到 35。第三轮 mid=18，18×18=324>144，r 到 17。第四轮 mid=9，9×9=81<144 偏小，l 抬到 10。第五轮 l=10、r=17，mid=13，13×13=169>144，r 到 12。第六轮 mid=11，11×11=121<144，l 抬到 12。第七轮 l=r=12，mid=12，12×12=144 相等，返回 true，七轮就从 [1,144] 逼到了 x=12。动画把范围缩到 1..14 演示，逼近道理一样。

mid×mid 冲破 int 上限，比较从此全反

每轮范围减半，最多约 log₂n 轮（n 是 num 大小），时间 O(log n)、空间 O(1)。最容易埋雷的是 mid×mid：num 接近 2³¹ 时平方冲破 32 位 int 上限、溢出成负数，本该偏大的判成偏小、方向反过来，得用 64 位 long 存 sq，或把比较改成 mid>num/mid 避开乘法。循环漏成 while l<r，l、r 撞到答案那格时直接跳出、少比一次，完全平方数会被误判成 false；偏小时只写 l=mid 不加 1，范围缩不动就死循环。

Python

def isPerfectSquare(num):
    l, r = 1, num               # 答案落在 1..num
    while l <= r:
        mid = (l + r) // 2
        sq = mid * mid
        if sq == num:           # 正好相等：找到了
            return True
        elif sq < num:          # 偏小：往右找
            l = mid + 1
        else:                   # 偏大：往左找
            r = mid - 1
    return False

C++

bool isPerfectSquare(int num){
    long l = 1, r = num;
    while (l <= r) {
        long mid = (l + r) / 2;
        long sq = mid * mid;     // long 防溢出
        if (sq == num) return true;
        else if (sq < num) l = mid + 1;
        else r = mid - 1;
    }
    return false;
}

Java

public boolean isPerfectSquare(int num) {
    long l = 1, r = num;
    while (l <= r) {
        long mid = (l + r) / 2;
        long sq = mid * mid;     // long 防溢出
        if (sq == num) return true;
        else if (sq < num) l = mid + 1;
        else r = mid - 1;
    }
    return false;
}