367. 有效的完全平方数

给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。 说明：不要使用任何内置的库函数，如 sqrt。 示例 1：

  1. 输入：16
  2. 输出：True

示例 2：

  1. 输入：14
  2. 输出：False

解题思路
改造一下 【 x的平方根】 这题 的二分递归版本就可以实现本题了

代码实现1
由findSqrt最后得到的平方根，再来进行一次计算判断从而确认输入是否为完全平方数

  1. //递归版的二分查找
  2. int findSqrt(int left,int right,int x){
  3.      int mid = (left+right)/2;
  4.      if(left > right)
  5.         return right;
  6.      if((long long)mid*mid <= x){
  7.         return findSqrt(mid+1,right,x);
  8.      }
  9.      else
  10.        return findSqrt(left,mid-1,x);
  11. }
  12. bool isPerfectSquare(int num){
  13.     int sqrtX = findSqrt(0,num,num);
  14.     if( (long long)sqrtX*sqrtX == num)
  15.         return true;
  16.     else 
  17.         return false;
  18. }

代码实现2
在递归过程中每一次算出的平方根做判断

  1. //递归版的二分查找
  2. bool findSqrt(int left,int right,int x){
  3.      int mid = (left+right)/2;
  4.      if(left > right)
  5.         return false;
  6.      if((long long)mid*mid == x)
  7.         return true;
  8.      else if((long long)mid*mid < x)
  9.         return findSqrt(mid+1,right,x);
  10.      else
  11.        return findSqrt(left,mid-1,x);
  12. }
  13. bool isPerfectSquare(int num){
  14.     return findSqrt(0,num,num);
  15. }