Valid Perfect Square

Description

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

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

 

Example 1:

Input: num = 16
Output: true

Example 2:

Input: num = 14
Output: false

 

Constraints:

• 1 <= num <= 2^31 - 1

Solution(javascript)

/** Newton's Method
 * @param {number} num
 * @return {boolean}
 */
// const isPerfectSquare = function (x) {
//   let r = x
//   while (r * r > x) {
//     r = Math.floor((r + x / r) / 2)
//   }

//   return r * r === x
// }

//  Binary Search
const isPerfectSquare = function (x) {
  let low = 0
  let high = x
  while (low <= high) {
    const middle = Math.floor((low + high) / 2)
    const current = middle * middle
    if (current === x) {
      return true
    } if (current < x) {
      low = middle + 1
    } else {
      high = middle - 1
    }
  }
  return false
}