判断完全平方数 - Python实现及优化

判断完全平方数：Python 高效算法实现

本文介绍如何判断一个正整数是否为完全平方数，并提供使用 Python 实现的二分查找高效算法，无需使用内置库函数如 sqrt。

什么是完全平方数？

完全平方数是指可以表示为某个整数与其自身的乘积的整数。例如，16 是完全平方数，因为它可以表示为 4 * 4。

问题描述

给定一个正整数 num，判断它是否为完全平方数。

示例

• 输入：num = 16

• 输出：True

• 解释：返回 True，因为 4 * 4 = 16，而 4 是一个整数。

• 输入：num = 14

• 输出：False

• 解释：返回 False，因为没有整数能够平方后等于 14。

解决方案：二分查找

为了高效地解决这个问题，我们可以使用二分查找算法。该算法的时间复杂度为 O(log(num))，其中 num 是给定的正整数。

代码示例 (Python)

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

# 测试示例
print(isPerfectSquare(16))  # 输出: True
print(isPerfectSquare(14))  # 输出: False

代码解释

1. 首先，我们处理特殊情况：如果 num 小于 2，则它一定是完全平方数，直接返回 True。
2. 然后，我们设置二分查找的搜索范围 [left, right]，初始值为 [1, num // 2]。
3. 在循环中，我们计算中间值 mid 以及 mid 的平方 square。
4. 如果 square 等于 num，则找到了完全平方数，返回 True。
5. 如果 square 大于 num，则需要缩小搜索范围到 [left, mid - 1]。
6. 如果 square 小于 num，则需要缩小搜索范围到 [mid + 1, right]。
7. 如果循环结束仍未找到完全平方数，则返回 False。

总结

本文介绍了使用二分查找算法判断完全平方数的高效方法，并提供了 Python 代码示例。该算法时间复杂度低，适用于处理大规模数据。