当前位置：首页 > news >正文

彻底弄懂二分查找的边界问题与模板

news 2026/5/23 9:41:17

引言

二分查找（Binary Search）是算法面试中最常见的题型之一，其核心思想极其简单：每次将搜索区间减半，直到找到目标值或者区间为空。

然而正如著名的计算机科学家高德纳（Donald Knuth）所言：“虽然二分查找的基本思想简单，但写出正确的代码却很困难。” 其中最大的痛点就在于边界的处理：

for l < r 还是 for l <= r？
r = mid 还是 r = mid - 1？
mid = l + (r-l)/2 还是 mid = l + (r-l+1)/2？

本文将结合寻找峰值的示例代码以及其他几种常见的二分类型，带你透彻理解二分查找的边界收缩逻辑。

类型一：寻找峰值元素（红蓝染色法 / 条件切分）

寻找数组的峰值元素（LeetCode 162）是一个非常经典的二分变体：数组无需有序，只要局部有序即可使用二分。

代码实现

首先来看我们规范化后的代码实现：

func findPeakElement(nums []int) int {l, r := 0, len(nums)-1// 当 l == r 时循环结束，此时 l 和 r 都指向峰值元素for l < r {mid := l + (r-l)/2// 如果中间元素大于其右侧元素，说明峰值在左侧（包含 mid）if nums[mid] > nums[mid+1] {r = mid} else {// 否则峰值在右侧（不包含 mid）l = mid + 1}}return l // 此时 l == r
}

边界解析

for l < r： 当我们寻找一个具体的极值或“具有某种属性的分界点”时，通常最后一定要得出一个唯一解。当 l == r 时，搜索区间只剩下一个数，它必然就是我们要找的数，因此不需要再进循环判断（再进循环会导致死循环）。
r = mid 与 l = mid + 1：
- 为什么 r = mid？因为当 nums[mid] > nums[mid+1]，mid 所在的元素有可能是峰值本身，所以缩减区间时必须包括 mid，即 [l, mid]。
- 为什么 l = mid + 1？当 nums[mid] <= nums[mid+1]，mid 肯定不可能是峰值（至少它的右边有个更大的），峰值只能在 mid 的右边，即区间 [mid+1, r]。
mid 取小： mid := l + (r-l)/2 在区间只有最后两个元素（例如 l=0, r=1）时，取的是偏左的值。由于我们的判断条件需要看 nums[mid+1]，如果 mid 偏右则 mid+1 会越界，因此 mid 必须偏左。

类型二：标准二分查找（寻找精确的 Target）

这是最基础的二分查找，在一个有序数组中寻找精确等于目标值 target 的索引。找到了返回索引，找不到返回 -1。

代码实现

func search(nums []int, target int) int {l, r := 0, len(nums)-1// 搜索区间为左闭右闭 [l, r]for l <= r { mid := l + (r-l)/2if nums[mid] == target {return mid // 直接找到，返回} else if nums[mid] > target {r = mid - 1 // 目标在左侧区间 [l, mid-1]} else {l = mid + 1 // 目标在右侧区间 [mid+1, r]}}return -1
}

边界解析

for l <= r： 我们的搜索区间是两端都闭合的 [l, r]。当 l = r 的时候，区间还有一个数字，这个数字还没被检查过，所以必须 l <= r 才能保证该数字被检查完毕。终止条件是 l = r + 1，即 []，此时搜索区间内没有任何元素。
r = mid - 1 与 l = mid + 1： 既然我们已经明确 nums[mid] != target，这就说明 mid 位置肯定不是我们要找的目标。下次搜索的区间自然就不应该包含 mid。

类型三：寻找下边界（第一个 >= target 的位置）

非常实用的二分类型，相当于 C++ 中的 std::lower_bound。

代码实现

func searchInsert(nums []int, target int) int {l, r := 0, len(nums)-1// 要找的解必定落在一个数上或数组的末尾之外ans := len(nums) // 默认值为所有元素都小于 target 的情况for l <= r {mid := l + (r-l)/2if nums[mid] >= target {ans = mid   // 记录潜在答案r = mid - 1 // 继续向左压缩，看有没有更早出现的} else {l = mid + 1 // 目标在右侧}}return ans
}

（也可以写成 l, r = 0, len(nums)配合 while l < r 的写法，不过记录 ans 的思路适应度更强）

总结：如何选择模板？

明确目标：
- 如果是找确定的值，用 [l, r] 闭区间，while(l <= r)，l = mid + 1, r = mid - 1，找到直接返回。
- 如果是需满足某个条件的边界/分界点（比如第一个峰值，第一个小于目标，最后一个等于目标的），可以记录答案 ans = mid 然后继续往另一个方向收缩，循环条件依然用 l <= r。或者使用 while (l < r) 搭配 l = mid + 1 / r = mid，让 l 和 r 相遇在答案处。
关于 mid 越界与死循环：
- 只要出现了在 else 里赋值 l = mid （区间停留在左侧不缩小），那么你的 mid 计算就必须取偏右：mid := l + (r-l+1)/2。否则当区间只有2个数如 [0,1] 时，偏左 mid 是 0，执行 l = mid 后区间依然是 [0,1]，从而陷入死循环。