二分搜索中何时返回low或high？求判断技巧

核心逻辑其实很简单：先搞清楚循环结束时low和high分别代表什么，再匹配题目的需求。

先明确二分搜索的终止状态 #

绝大多数二分搜索的终止条件是low > high，这时候两个指针的位置关系是：high在low的左边一位，且两者分别对应两种边界情况。

结合具体题目拆解 #

1. 求平方根（向下取整） #

题目需求：找最大的整数x，使得x² ≤ 输入值n。
对应的二分指针逻辑：

• 当mid² > n：mid太大，往左缩范围，high = mid - 1
• 当mid² ≤ n：mid可能是候选，但还能找更大的，往右缩范围，low = mid + 1

循环结束时：

• high是最后一个满足x² ≤n的位置（也就是我们要的答案）
• low是第一个满足x² >n的位置（比答案大1）
  所以这时候返回high。

2. 搜索插入位置 #

题目需求：找到目标值的索引；如果不存在，找到第一个大于等于目标值的位置（即插入点）。
对应的二分指针逻辑：

• 当nums[mid] < target：mid太小，往右缩范围，low = mid + 1
• 当nums[mid] ≥ target：mid可能是候选，往左缩范围，high = mid - 1

循环结束时：

• low是第一个大于等于target的位置（正好是插入点或目标值索引）
• high是最后一个小于target的位置（比插入点小1）
  所以这时候返回low。

通用判断技巧 #

1. 先明确题目核心需求：
   • 如果要找最大的满足条件的元素（比如平方根的向下取整）→ 返回high
   • 如果要找最小的满足条件的元素/插入位置（比如搜索插入点）→ 返回low
2. 手动走一遍边界测试用例验证：
   比如求平方根时n=2，手动模拟循环：
   • 初始low=0, high=2 → mid=1，1²≤2 → low=2
   • mid=(2+2)//2=2，2²>2 → high=1
   • 此时low=2>high=1，返回high=1，正确。
     搜索插入位置时nums=[1,3,5], target=2：
   • 初始low=0, high=2 → mid=1，nums[1]=3>2 → high=0
   • mid=0，nums[0]=1<2 → low=1
   • 此时low=1>high=0，返回low=1，正确。

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