367. 有效的完全平方数
这道题目真的看起来极其简单的，就是判断一个数字是不是完全平方数，比如 16 是 4 的平方，9 是 3 的平方。可惜，愚笨如我，能想出来的方法，只有一个，就是从 1 开始求平方，然后逐一去比较，不能更蠢了吧？就是穷举法。
于是我去看题解，还有什么解法，才知道，原来这么简单的一道题目有那么多种解法的。官方题解里说可以用“递归”，我是完全没想出来的，官方的题解里也没列举，所以只好作罢了。直接说说二分查找法吧。
其实，从 1 开始逐一去求平方，然后尝试，这个方法，已经接近了二分查找法了，既然能想到顺序逐一穷举，就自然能想到二分查找啊，两大要素是：1，有序；2，逐一遍历；妈呀，我为啥想不到，还是太浮躁。
另外，让人头痛的是，二分法真的很不好写。每个人都可以轻飘飘说句，二分呀，你试试直接一口气写对？上下标直接叫人疯狂，每次我狂推理搞明白了，过几个月，就又回到了从前。
如果我们要用二分法的话，那么首先要知道起始和终止的位置，然后用二分法解决。起始位置很容易判定，就是 0，终点呢，是 num 本身么？也未尝不可，不过，如果稍微对数字有点感觉，就知道到，只要到 num/2 就可以了。证明起来也很容易，就是证明这个不等式：[
\sqrt{n} \leq \frac{n}{2}
]可以看出，在 n > 4 的时候，显然是成立的，在 1 < n < 4 的时候，也不会妨碍程序的正确性。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution:
def isPerfectSquare(self, num: int) -> bool:
if num == 0 or num == 1:
return True
start = 0
end = num // 2
# 这里使用闭区间[start, end]
while start <= end:
mid = ( start + end ) // 2
sqr = mid * mid
if sqr > num:
end = mid - 1
elif sqr < num:
start = mid + 1
else:
return True
return False
关于二分法怎么能一次写正确，以前我也看过，自己也反思过，不过还是忘记了，这次我又是打开谷歌搜索来搜的“怎么才能把二分法写正确”，这次搜的文章，我觉得讲得挺清楚的，没有各种“酷炫”的比喻，就是很抽象地硬是给你讲清楚了《二分法其实很简单，为什么老是写不对！》，这里推荐一下。
把握住一个关键点，就是循环不变量。关键在于你怎么理解你的搜索区间，根据你对区间的理解，来决定用 < 还是用 <=，用 +1 还是用 -1，虽然，循环不变量的概念很抽象，开闭区间的概念也很抽象，但是，这个说法确实是准确和好用的，判断起来也比较容易。咱们写代码还是期望能快速的写对才是正事。
第二种比较高级的解法，是使用牛顿迭代法，大家自己去看就行了，我就不写了。我觉得，牛顿迭代法首先就要求比较高的数学功底，而且，就算你数学层面懂了，还要知道数学层面怎么才能转化成代码。这个题目里，函数正好是一个平方函数，而且函数的根正好收敛。在函数二阶不可导的情况下，是不能使用牛顿迭代法的，而且初次 guess 选点如果碰巧选到了二次曲线的顶点也是要糟糕的，LC 给出的算法，什么都没考虑，就直接正确了。要么是他运气好到炸裂，要么就是确实那些人家都考虑了，没有处理的必要，所以写出来才能如此间接。但是就好像那个画马，“增加一些细节”的步骤，你不会的话，你永远画不出一匹马的。
第三种解法，我看在 LC 上，真的点赞很多，底下网友都说机智，这也是对数学有着非常敏锐的感觉的人，才能想出来的妙法。奇数等差数列的和，正好是序号的平方。也即，1 到第 k 个奇数的求和，正好等于 1
2
3
4
5
6
7
8
9class Solution:
def isPerfectSquare(self, num: int) -> bool:
if num < 2:
return True
i = 1
while num > 0:
num -= i
i += 2
return num == 0
这个真是绝了，简短而且健壮，几乎不容易写错。不过那个灵光一闪，不是每个人都能想出来的。