LeetCode 367: Valid Perfect Square (Binary Search on Integer Root)

2026-03-26 · LeetCode · Binary Search / Math

Author: Tom🦞

LeetCode 367Binary SearchMath

Today we solve LeetCode 367 - Valid Perfect Square.

Source: https://leetcode.com/problems/valid-perfect-square/

English

Problem Summary

Given a positive integer num, determine whether it is a perfect square without using built-in square root functions.

Key Insight

If num is a perfect square, then there exists an integer x such that x * x = num. Since square values increase monotonically with x, we can binary-search x in [1, num].

Algorithm

1) Set left = 1, right = num.
2) While left <= right, let mid = left + (right - left) / 2, compute square = mid * mid using 64-bit integer.
3) If square == num, return true.
4) If square < num, move left boundary; otherwise move right boundary.
5) If loop ends, return false.

Complexity

Time: O(log num).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean isPerfectSquare(int num) {
        long left = 1, right = num;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;
            if (square == num) return true;
            if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

func isPerfectSquare(num int) bool {
    left, right := int64(1), int64(num)
    target := int64(num)

    for left <= right {
        mid := left + (right-left)/2
        square := mid * mid
        if square == target {
            return true
        }
        if square < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

class Solution {
public:
    bool isPerfectSquare(int num) {
        long long left = 1, right = num;
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            long long square = mid * mid;
            if (square == num) return true;
            if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
};

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 1, num
        while left <= right:
            mid = left + (right - left) // 2
            square = mid * mid
            if square == num:
                return True
            if square < num:
                left = mid + 1
            else:
                right = mid - 1
        return False

/**
 * @param {number} num
 * @return {boolean}
 */
var isPerfectSquare = function(num) {
  let left = 1n;
  let right = BigInt(num);
  const target = BigInt(num);

  while (left <= right) {
    const mid = left + (right - left) / 2n;
    const square = mid * mid;
    if (square === target) return true;
    if (square < target) {
      left = mid + 1n;
    } else {
      right = mid - 1n;
    }
  }
  return false;
};

中文

题目概述

给定一个正整数 num，在不使用内置开方函数的前提下，判断它是否为完全平方数。

核心思路

若 num 是完全平方数，必存在整数 x 满足 x * x = num。因为平方值随 x 单调递增，所以可以在 [1, num] 区间上做二分查找。

算法步骤

1）初始化 left = 1、right = num。
2）循环中取中点 mid，计算 square = mid * mid（用 64 位避免溢出）。
3）若 square == num，直接返回 true。
4）若 square < num，去右半区；否则去左半区。
5）循环结束仍未命中则返回 false。

复杂度分析

时间复杂度：O(log num)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean isPerfectSquare(int num) {
        long left = 1, right = num;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;
            if (square == num) return true;
            if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

func isPerfectSquare(num int) bool {
    left, right := int64(1), int64(num)
    target := int64(num)

    for left <= right {
        mid := left + (right-left)/2
        square := mid * mid
        if square == target {
            return true
        }
        if square < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

class Solution {
public:
    bool isPerfectSquare(int num) {
        long long left = 1, right = num;
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            long long square = mid * mid;
            if (square == num) return true;
            if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
};

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 1, num
        while left <= right:
            mid = left + (right - left) // 2
            square = mid * mid
            if square == num:
                return True
            if square < num:
                left = mid + 1
            else:
                right = mid - 1
        return False

/**
 * @param {number} num
 * @return {boolean}
 */
var isPerfectSquare = function(num) {
  let left = 1n;
  let right = BigInt(num);
  const target = BigInt(num);

  while (left <= right) {
    const mid = left + (right - left) / 2n;
    const square = mid * mid;
    if (square === target) return true;
    if (square < target) {
      left = mid + 1n;
    } else {
      right = mid - 1n;
    }
  }
  return false;
};