P174 验证完全平方数

描述#

这个题目说的是，给你一个正整数 num，你要实现一个函数，来判断它是否为完全平方数。

注意，不能使用内置的平方根函数（sqrt）。

比如说，给你的正整数是 9，
num = 9
9 是 3 的平方，因此 9 是一个完全平方数，返回 true。
再比如说，给你的正整数是 8，
num = 8
8 不是一个完全平方数，返回 false。

相关视频：实现平方根函数

代码#

public class AlgoCasts {

  // Time: O(log(num)), Space: O(1)
  public boolean isPerfectSquareBinarySearch(int num) {
    long low = 1, high = num;
    while (low <= high) {
      long mid = low + (high - low) / 2;
      long mid2 = mid * mid;
      if (mid2 == num) return true;
      else if (mid2 > num) high = mid - 1;
      else low = mid + 1;
    }
    return false;
  }

  // Time: O(log(num)), Space: O(1)
  public boolean isPerfectSquareNewton(int num) {
    long x = num;
    while (x*x > num) {
      x = (x + num/x) / 2;
    }
    return x*x == num;
  }

}