二分法(binary search)

二分法本质上是是一种快速搜索策略。核心是每次将搜索空间平均分成两份，确定问题集中其中一个区间，继续将空间平分以确定问题所在, 主要操作是将问题空间二分。

给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。

说明：不要使用任何内置的库函数，如 sqrt。

示例 1：

1 2	输入：16 输出：True

实例2：

1 2	输入：14 输出：False

由于题目已要求不允许使用sqrt方法。
先看数学方法：
根据公式 1 + 3 + 5 + 7 +… +(2n-1) = n^2 即完全平方数肯定是前n个连续奇数的和。即只需要计算前N个奇数之和是否正好于输入值相等即可。
时间复杂度On 该题目最多计算 46340 / 2次加法

再看二分法：
首先要知道一个前提，整型底数上限为46340 即整数最大值为 2147483647 而其中最大的有效的完全平方数为 46340 * 46340 = 2147395600
使用二分法查找num的根

步骤1 left = 0 right = 46340 middle = (left + right) / 2
步骤2 middle * middle / 2 的平方和给定值比较大小
步骤3 根据大小确定二分区间如果 middle * middle / 2 的平方和 > 给定值即可能解在[middle - right]区间内反之则在[left - middle]区间内。
步骤4 (right || left) = middle middle = (left + right) / 2
重复步骤 2 3 4。直到找到最终解或最终确定无解。

时间复杂度 logn 该题目最多计算15次平方数。