二分查找变体题通用解题框架求助：以非负整数求截断平方根为例

• 第一步：明确搜索目标的判定条件，先把你要找的结果的准确定义写出来，比如本题就是「最大的整数res，满足res² ≤ x」，不要模糊定义。
• 第二步：确定搜索区间类型，推荐优先用新手不容易出错的「左闭右闭」区间[lo, hi]，初始边界严格覆盖所有可能的结果取值范围。
• 第三步：定义循环不变式，明确每次循环开始时，搜索区间和目标值的对应关系，整个搜索过程都要严格遵守这个规则，不能出现逻辑漂移。
• 第四步：匹配循环终止条件和指针移动规则，左闭右闭区间对应循环条件为while lo <= hi，每次判断mid是否符合条件后，严格排除不可能存在目标的半区：如果目标不可能在左半区就把lo设为mid + 1，不可能在右半区就把hi设为mid - 1，不要出现区间遗漏或者重叠。
• 第五步：确定循环结束后的返回值，根据循环不变式推导终止状态（左闭右闭区间终止时lo = hi + 1）下哪个变量符合你一开始定义的目标条件。
• 第六步：用3-4个边界用例验证逻辑，比如最小值、最大值、刚好命中目标、刚好不命中目标的情况，不需要大量用例就能排查逻辑漏洞。

现有代码的问题 #

你额外引入了mid + 1的平方作为判断值，逻辑绕了一层，且循环结束后直接返回mid + 1不符合循环终止时的变量状态，比如x=2时循环终止mid为1，返回1+1=2就会出错。

正确的循环不变式 #

首先明确我们的搜索目标是「最大的整数res，满足res² ≤x」，我们采用左闭右闭区间[lo, hi]，对应的循环不变式为：

所有小于lo的整数的平方都 ≤ x，所有大于hi的整数的平方都 > x，我们要找的目标值一定落在当前[lo, hi]区间内。

正确实现代码 #

class Solution:
    def mySqrt(self, x: int) -> int:
        lo = 0
        hi = x
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            square = mid * mid
            if square == x:
                return mid
            elif square < x:
                # mid是候选解，尝试找更大的符合条件的值
                lo = mid + 1
            else:
                hi = mid - 1
        # 循环终止时lo = hi + 1，hi就是最后一个满足平方<=x的数
        return hi

用例验证 #

• 输入x=2：循环结束时hi=1，返回1，符合要求
• 输入x=7：循环结束时hi=2，返回2，符合要求
• 输入x=8：循环结束时hi=2，返回2，符合要求
• 输入x=4：循环中直接命中mid=2，返回2，符合要求

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