如何用Python二分查找实现向下取整平方根计算

原有代码问题 #

• 语法错误：比较运算符写反，=> 需改为>=
• 逻辑错误：两个独立if判断会导致mid值被重复修改，区间更新逻辑缺失，没有正确维护查找的上下边界

正确实现代码 #

def find_sqrt(k):
    # 边界处理：k为0时直接返回0
    if k == 0:
        return 0
    begin, last = 1, k
    res = 0
    while begin <= last:
        mid = (begin + last) // 2
        mid_square = mid * mid
        if mid_square == k:
            return mid
        elif mid_square < k:
            # 当前mid符合小于平方根的条件，暂存结果
            res = mid
            # 向右半区间找更大的符合要求的值
            begin = mid + 1
        else:
            # mid平方过大，向左半区间找
            last = mid - 1
    return res

效果验证 #

• find_sqrt(101) 返回值为10
• find_sqrt(100) 返回值为10

实现说明 #

二分查找过程中每次比较中间值平方和目标值的大小，动态收缩查找区间：

• 当中间值平方小于目标值时，记录当前中间值为候选结果，继续向右区间寻找更大的符合要求的整数
• 当中间值平方大于目标值时，直接向左区间收缩
• 遇到完全相等的情况直接返回中间值，就是精确平方根

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