二分查找基础：循环条件与边界更新规则相关疑问

你没有遗漏核心基础知识，这两类用法的区分是二分查找落地实现时的高频易错点，本质和你定义的搜索区间规则、要实现的查找目标直接相关，梳理清楚对应关系就不会混淆。

一、循环终止条件的选择 #

两种写法对应不同的查找场景：

• while (left <= right)：适用于在闭区间[left, right]中查找是否存在某个确定的目标值的场景。此时每次循环的搜索范围都是左右闭合的，区间内的所有元素都还没有被排除。当left > right时，闭区间内已经没有剩余元素，说明目标不存在，可以直接终止循环。
• while (left < right)：适用于查找满足条件的边界值的场景，比如找第一个大于等于目标值的下标、最后一个小于目标值的下标等。循环终止时left和right会重合，这个重合的位置就是要找的目标边界，不需要额外判断返回左还是右。

二、边界更新规则的选择 #

边界更新规则必须和你定义的搜索区间逻辑保持一致，否则会出现死循环或者漏查元素的问题：

1. 搭配while (left <= right)（闭区间存在性查找）的规则 #

此时搜索区间是闭区间，已经判断过不满足条件的mid要完全排除出区间：

• 当nums[mid] > target：说明mid位置的元素一定不是目标，目标只可能出现在mid左侧，因此更新right = mid - 1
• 当nums[mid] < target：说明mid位置的元素一定不是目标，目标只可能出现在mid右侧，因此更新left = mid + 1
• 当nums[mid] == target：直接返回mid即可

2. 搭配while (left < right)（边界查找）的规则 #

此时需要保留可能作为边界的mid在搜索区间内，根据查找的是左边界还是右边界调整规则：

查找左边界（例：第一个大于等于target的位置）

• 当nums[mid] >= target：说明mid可能是目标边界，也可能目标边界在mid左侧，需要保留mid在区间内，因此更新right = mid
• 当nums[mid] < target：说明mid一定不是目标边界，目标在mid右侧，因此更新left = mid + 1
  该场景下mid默认使用向下取整的计算方式mid = left + (right - left) / 2即可，不会出现死循环

查找右边界（例：最后一个小于等于target的位置）

• 当nums[mid] <= target：说明mid可能是目标边界，也可能目标边界在mid右侧，需要保留mid在区间内，因此更新left = mid
• 当nums[mid] > target：说明mid一定不是目标边界，目标在mid左侧，因此更新right = mid - 1
  注意：该场景下mid必须使用向上取整的计算方式mid = left + (right - left + 1) / 2，否则当left和right相邻时，mid会取到left，如果刚好满足nums[mid] <= target，就会一直执行left = mid陷入死循环

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