Jovian DSA Binary Search查找查询值首次出现时无限循环问题咨询

核心故障原因 #

1. 边界更新逻辑未正确收缩区间 #

这是出现无限循环的最高频原因

当你在二分过程中命中目标值cards[mid] == target时，为了找首次出现的位置，需要向左搜索，所以应该把右边界调整为mid而非mid - 1。如果此时你对未命中场景的边界调整逻辑错误，比如把左边界更新为mid而非mid + 1，就会出现区间无法收缩的情况：比如只剩两个相同的目标值[target, target]时，mid值会一直固定在同一个位置，边界永不重合，程序就会卡死在循环里。

2. mid计算方式和边界逻辑不匹配 #

如果你用向下取整的mid计算方式mid = (low + high) // 2，配合命中目标时high = mid、未命中时low = mid + 1的逻辑是完全没问题的；但如果你误用了向上取整的mid计算方式mid = (low + high + 1) // 2，又同时在命中目标时调整右边界为mid，就会在区间只剩两个元素的时候永远无法退出循环。

3. 递归实现缺少正确的终止条件 #

递归版本如果漏掉了low > high的终止判断，或者终止条件的阈值写错，比如错写为low >= high但边界逻辑不匹配，就会导致递归永远无法触达终止节点，持续递归调用，外部表现和无限循环一致。

后续规避方案 #

• 先明确区间定义：统一使用左闭右闭[low, high]或者左闭右开[low, high)的区间规则，全程不要变更逻辑
• 固定首次出现位置的二分逻辑：如果使用左闭右闭区间，命中目标时high = mid，cards[mid] < target时low = mid + 1，mid用mid = low + (high - low) // 2的方式计算，既避免整数溢出也适配向下取整的逻辑
• 写完逻辑后先做最小用例验证：手动模拟区间只剩1个元素、2个元素的执行流程，确认区间每次都在收缩，不会出现卡住不动的情况
• 递归实现优先写终止条件，再写业务逻辑，避免漏写终止判断

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