10-14 LeetCode 367. Valid Perfect Square
Description
Given a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as sqrt.
写一个方法判断一个数是不是平方数。
不使用内置库中的函数。
Example 1:
Input: 16
Returns: True
Example 2:
Input: 14
Returns: False
Solution 1:
这个题目看上去就非常简单，但是我第一次提交的代码就超时了，我想大多数人都会像我一样，第一个想到的算法是优化后的穷举，但是当数字太大时循环次数还是太多，导致超时。超时后想改进一下算法，发现还是有一些难度的。
第一个方法是与数学有关，高中还是初中学的等差数列求和。一个以1做首项，2为公差的等差数列的和为n*n。
a[1] = 1, a[2] = 3, a[n] = a[n-1] + 2
a[1] + a[2] + ... + a[n] = 1 + 3 + 5 + ... + 2*n-1
= n * n
然后很自然而然的有了下面的代码：
class Solution(object):
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
result = 0
i = 1
while result < num:
result += i
i += 2
if result == num:
return True
return False
Solution 2:
第一个方法的运行速度很慢，也不是我自己想出来的。因为高中数学知识已经还给体育老师了。
我自己后来想到的方法是二分法，类似于二分查找，只是在判断等于条件时与二分查找有些区别。但这些都不是重点，介绍这个方法的重点是如何写好一个二分查找。二分查找的思路都是一样的，但是在代码实现上一些细节的改变也会改变二分查找的效率。
我写的这个二分发是我在看《代码之美》时看到的，我的代码与书上还有些区别，毕竟我是求平方，所以直接用《代码之美》上的二分来解释为什么这个二分比较好。
《代码之美》上的二分是Java写的，我改写成Python。算法部分没有区别！
def binarySearch(lists, target):
low, high = -1， len(lists)
while high - low > 1:
mid = (low + high) >>> 1
mid_val = lists[mid]
if mid_val < target:
low = mid
elif mid_val > target:
high = mid
if low == -1 or lists[low] != target:
return -1
return low
最重要的地方是程序在循环中没有判断是否找到目标值。《代码之美》是这样解释的。
假设我们有一个N个元素的数组（N值很大），那么从该数组中第一次找到目标的概率为1/N（一个很小的数值），下一次为1/(N/2)，仍然不是很大，以此类推下去，只有当元素个数减少到10到20时，以此找到目标的概率才有意义，而对于10到20个元素进行查找大概需要4次循环，当查找失败时（在大多数应用中很普遍），那些额外的测试会编程额外开销。所以省去判断，只在最后进行是否找到目标值得判断。
感想
即使一个简单的算法也值得去深究，当数据变大时，小的优化也很关键
