二分查找解处于边界时的处理问题——以threeSumClosest为例

核心误区：混淆双指针遍历与二分查找的适用场景 #

你遇到的问题本质是把两种逻辑完全不同的策略搞混了：threeSumClosest用的是双指针逐步遍历组合，而l=mid+1/r=mid-1是二分查找的跳跃式缩区间逻辑，两者的目标和适用场景完全不匹配。

为什么mid更新方式会出错 #

threeSumClosest的双指针解法，核心是利用数组有序的特性，逐个试探区间内的所有两数组合：

• 当当前三数和小于target时，右移左指针增大和；
• 当当前三数和大于target时，左移右指针减小和；
  这种逐步移动的方式不会错过任何可能更接近target的组合。

而二分查找的l=mid+1/r=mid-1是为了快速定位精确匹配的目标值，它会直接跳过mid的一侧区间。但找“最接近值”的场景中，最优解可能存在于mid的任意一侧，跳过某一侧必然会遗漏候选组合。比如：
nums=[1,2,4,8,16], target=10，固定第一个数1后，用二分逻辑会直接跳过包含2和8的区间，漏掉最优解1+2+8=11。

正确的处理方式 #

1. 优先用双指针策略
   对于threeSumClosest这类需要遍历区间组合找最优解的问题，双指针逐步移动的方式是最适配的——时间复杂度O(n²)，逻辑简单且不会遗漏任何候选组合，就是你给出的示例代码那种写法。

2. 若尝试二分思路，需调整逻辑
   如果非要用二分优化，不能直接跳过区间，而是要保留双向搜索的可能：

   • 计算mid位置的三数和（固定第一个数 + nums[mid] + nums[r] 或 固定第一个数 + nums[l] + nums[mid]）
   • 比较当前mid组合与最优解的距离，更新最优解
   • 根据mid组合和target的大小关系，决定优先搜索左半区还是右半区，但不能直接丢弃另一侧
     不过这种方式的效率并不比双指针高，反而逻辑更复杂，没必要舍近求远。

3. 明确算法适用边界

   • 二分查找：适合精确查找目标值、找边界值（比如第一个大于target的数）等场景，要求目标有唯一性或明确边界。
   • 双指针：适合有序数组中和相关的组合问题（最接近、等于目标值、组合数量等），需要遍历区间内的组合来比较优劣。

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