如何用Python bisect求完全平方根并判断是否为完全平方数？

原来的代码通过bisect_left找到的是第一个满足v*v >= num的整数位置，但无法区分该位置的平方是否恰好等于输入值。要实现“找到准确平方根返回对应整数，否则返回-1/None”的需求，只需在拿到bisect的结果后增加一步验证即可。

修改后的代码 #

import bisect

def squareRootUsingBisect(num):
    if num == 0:
        return 0
    # 用range替代列表，节省内存（Python 3.10+支持key参数）
    idx = bisect.bisect_left(range(num + 1), num, lo=0, hi=num, key=lambda v: v*v)
    # 验证找到的数的平方是否等于原数
    return idx if idx * idx == num else -1

# 测试用例
print(squareRootUsingBisect(169))  # 输出：13
print(squareRootUsingBisect(170))  # 输出：-1
print(squareRootUsingBisect(0))    # 输出：0
print(squareRootUsingBisect(1))    # 输出：1
print(squareRootUsingBisect(25))   # 输出：5
print(squareRootUsingBisect(26))   # 输出：-1

关键说明 #

• bisect_left的作用是找到第一个让key(v) >= num的位置，对于非完全平方数，这个位置的平方会大于输入值，因此需要验证idx*idx == num来确认是否是准确的平方根。
• 用range(num+1)代替list(range(0,num))可以避免生成大列表，提升内存效率，尤其当num取值很大时效果明显。
• 如果需要返回None而非-1，只需把返回语句改成return idx if idx * idx == num else None即可。

内容的提问来源于stack exchange，提问作者Rnj