367. 有效的完全平方数

367. 有效的完全平方数

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
输入：num = 16
输出：true

• 时间复杂度：O(logN)。

• 空间复杂度：O(1)。

  //二分法
  func isPerfectSquare(num int) bool {
    if num == 1 {
        return true
    }
    left , right := 1, num
    for right >= left {
        mid := left + (right -left) >> 1
        if mid * mid > num {
            right = mid -1 
        } else if mid * mid < num {
            left = mid + 1
        } else {
            return true
        }
    }
    return false 
  }

• 时间复杂度：O(logN)。

• 空间复杂度：O(1)。

  //牛顿迭代法
  func isPerfectSquare(num int) bool {
    if num == 1 {
        return true
    }
  
    r := num/2
    for r * r > num {
        r = (r + num/r) / 2
    }
    if r * r == num {
        return true
    }
    return false
  }