竞赛编程中如何确定二分查找的上下界？Topcoder教程相关疑惑

嘿，我太懂这种困惑了——当年刚啃二分查找的时候，我对着上下界的设定纠结了好几天，总怕设错导致死循环或者答案跑偏。其实核心逻辑没那么复杂，关键是先锚定你的目标，再结合问题的边界条件来框定初始范围。下面我拆解一下我的思路，你可以参考：

在设上下界之前，一定要先搞清楚你要找的是什么：

• 是数组中第一个满足条件的元素？
• 还是最后一个满足条件的元素？
• 或者是某个数值层面的最值（比如最小的满足X条件的数、最大的不超过Y阈值的数）？

不同的目标会直接影响上下界的初始设定和后续的收缩逻辑，这是第一步，别跳过。

1. 从“极端情况”覆盖所有可能答案 #

上下界的核心要求是：这个范围里必须包含你要找的正确答案，哪怕范围大一点也没关系——毕竟二分是对数复杂度，哪怕上界设成1e18，也只需要60次左右的循环，完全不会超时。

举几个常见例子：

• 如果是数组索引二分（比如找数组里的元素位置）：下界直接设0（数组起始索引），上界设n-1（数组末尾索引），这是最基础的情况。如果是找插入位置（比如所有元素都小于目标值时要插在末尾），上界就得设成n而不是n-1。
• 如果是数值二分（比如找满足条件的最小k值）：下界设问题允许的最小可能值，上界设问题允许的最大可能值。比如题目说k是正整数，那下界可以设1；如果没明确限制，就往大了设（比如1e9，反正不影响效率）。

2. 利用题目约束缩小初始范围 #

如果题目给了明确的数值约束，那就用这些约束来让初始范围更精准（虽然不影响效率，但代码会更严谨）。比如题目说“数组元素的取值范围是[1, 100]”，那找某个数值的话，上下界可以直接设1和100，不用再设1e9。

3. 特殊边界要提前考虑 #

有些场景下答案可能在常规范围的边缘，比如：

• 找第一个大于target的元素，如果数组所有元素都小于target，答案应该是数组长度（插入到末尾），这时候上界必须设为n而不是n-1。
• 找最大的满足f(x) <= target的x，如果所有x都满足，那答案就是上界的最大值；如果都不满足，可能需要返回-1或者题目指定的特殊值。

场景1：数组索引二分（找元素位置） #

比如经典的“找第一个等于target的元素”：

• 初始上下界：left = 0，right = n-1
• 二分逻辑：如果nums[mid] < target，说明答案在右边，left = mid + 1；否则right = mid
• 循环终止条件：left < right，最后left就是目标位置（需要额外检查是否等于target，防止不存在的情况）

如果是“找最后一个等于target的元素”：

• 初始上下界：left = 0，right = n-1
• 二分逻辑：如果nums[mid] > target，说明答案在左边，right = mid - 1；否则left = mid
• 循环终止后检查nums[right]是否等于target即可。

场景2：数值二分（找满足条件的最值） #

比如竞赛常考的“珂珂吃香蕉”问题：珂珂每小时吃k根香蕉，要在H小时内吃完所有香蕉，求最小的k。

• 上下界设定：下界是1（每小时最少吃1根），上界是数组中最大的香蕉数（每小时吃最多的那堆，肯定能在H小时内吃完）
• 二分逻辑：计算当前k下吃完所有香蕉需要的时间，如果时间<=H，说明可以尝试更小的k，right = mid；如果时间>H，说明k太小了，left = mid + 1
• 最后left就是最小的k值。

再比如“分割数组的最大值”：把数组分成m段，求各段和的最大值的最小值。

• 上下界设定：下界是数组中最大的元素（因为每段至少要能装下最大的那个元素），上界是数组所有元素的和（分成1段的情况）
• 二分逻辑：判断当前最大值是否能把数组分成不超过m段，如果可以，尝试更小的最大值，right = mid；如果不行，left = mid + 1。

• 别害怕初始范围太大：二分的效率真的很高，哪怕上界是1e18，循环次数也不会超过70次，完全不用担心超时。
• 注意循环终止条件：一般用left < right更稳妥，避免死循环。如果用left <= right，一定要注意更新left或right的时候要加1或减1（比如left = mid + 1而不是left = mid）。
• 验证边界情况：写完代码后，一定要测试极端情况——比如所有元素都满足条件、所有元素都不满足条件、答案在范围边缘的情况，确保上下界的设定能覆盖这些场景。

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