367. Valid Perfect Square

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

判断一个数是不是某个数的平方。

对于一个给定的正整数n，我们可以从x = 1枚举到x = n，计算x^2然后与n比较，这样暴力解决。结果肯定是超时的。

以上，我们构成了一个有序的序列1....n，这不正是二分法的前提条件么？

package _367;

/**
 * 367. Valid Perfect Square
 */
public class Solution {
    public boolean isPerfectSquare(int num) {
        long left = 1;
        long right = num;
        while (left <= right) {
            long mid = left + ((right - left) >> 1);
            if (mid * mid < num) {
                left = mid + 1;
            } else if (mid * mid > num) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isPerfectSquare(2147483647));
    }
}

因为输入存在形如2^31 -1这样大的数，中间结果我们需要用long保存。

相应的：

69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

package _69;

public class Solution {
    public int mySqrt(int x) {
        int left = 1;
        int right = x;
        while (left <= right) {
            long mid = left + ((right - left) >> 1);
            if (mid * mid < x) {
                left = (int)mid + 1;
            } else if (mid * mid > x) {
                right = (int)mid - 1;
            } else {
                return (int) mid;
            }
        }
        return right;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.mySqrt(13));
    }
}