367. Valid Perfect Square

Problem

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
Output: true

Example 2:

Input: 14
Output: false

Summary

Given a positive integer num, write a function that returns True if num is a perfect square, otherwise returns False.

Note: Do not use any built-in library function such as sqrt.

Solution Approach

• Given a number, determine whether it is a perfect square.
• Binary search can be used to solve this problem. To determine a perfect square, follow its definition: whether its square root can be taken, that is, whether there exists a number whose square equals the number to be judged. Perform binary search in the interval [1, n]. If such a number can be found, return true; if not, return false.

Code

package leetcode

func isPerfectSquare(num int) bool {
	low, high := 1, num
	for low <= high {
		mid := low + (high-low)>>1
		if mid*mid == num {
			return true
		} else if mid*mid < num {
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return false
}