1. 从“边界”说起：为什么二分查找总让人纠结

如果你写过二分查找，大概率经历过这样的时刻：代码看起来逻辑清晰，但一运行，要么是死循环，要么是漏掉目标值，要么干脆数组越界。调试半天，发现只是把while (left <= right)改成了while (left < right)，或者把right = mid - 1改成了right = mid。这些看似微不足道的改动，背后隐藏的正是二分查找最核心也最容易混淆的概念——区间定义，也就是我们常说的“左闭右闭”、“左闭右开”和“左开右闭”。

很多人第一次学二分，都是从“在有序数组中找一个数”的经典场景开始的。教科书或者教程通常会给出一个“标准”模板，告诉你照着写就行。但一旦问题稍微变化，比如要找第一个大于等于目标值的位置，或者最后一个小于目标值的位置，套用原来的模板就很容易出错。这时候，如果你不理解你代码中left和right所代表的搜索区间的确切含义，以及这个区间是如何随着比较结果收缩的，调试就会变成一场噩梦。

我最初也踩过不少坑，后来才明白，二分查找的本质不是背模板，而是理解并维护一个循环不变量。这个不变量就是：在每一轮循环开始时，目标值（如果存在）一定在当前定义的搜索区间内。而我们所有关于left、right、mid的更新操作，都必须紧紧围绕着维护这个不变量来进行。左闭右闭、左闭右开、左开右闭，就是三种最常见的区间定义方式，它们对应着不同的初始化、循环条件和更新逻辑。选哪一种本身没有绝对的对错，但一旦选定，就必须保持逻辑上的一致性，否则不变量就会被破坏，算法自然就错了。

更进一步的，理解这些区间划分，能帮助我们洞察二分查找的“两段性”。这是将二分法从“查找一个值”推广到“查找一个分界点”这类更广泛问题的关键。今天，我们就彻底把这两个问题掰开揉碎，让你下次写二分时，不再是凭感觉和记忆，而是真正理解每一行代码背后的意图。

2. 三种区间定义的代码实现与逻辑对比

让我们先抛开抽象概念，直接看代码。假设我们有一个升序数组nums和一个目标值target，实现最基础的二分查找。我们会看到三种不同的写法，其核心区别就在于对搜索区间[left, right]的理解。

2.1 左闭右闭区间[left, right]

这是最符合直觉的区间表示法。left和right初始化时，分别指向数组的第一个和最后一个元素的索引。这意味着，搜索区间从一开始就包含了所有可能的元素。

int binarySearch_close(vector<int>& nums, int target) { int left = 0; // 区间左边界，包含 int right = nums.size() - 1; // 区间右边界，包含 while (left <= right) { // 关键：因为区间有效时，left == right 是有意义的（区间内还有一个元素） int mid = left + (right - left) / 2; // 防止溢出 if (nums[mid] == target) { return mid; // 找到目标 } else if (nums[mid] < target) { // 目标在右侧，mid 已经检查过且不是，所以新区间从 mid+1 开始 left = mid + 1; } else { // nums[mid] > target // 目标在左侧，mid 已经检查过且不是，所以新区间到 mid-1 结束 right = mid - 1; } } // 循环结束，说明 left > right，区间为空，未找到 return -1; }

关键点解析：

1. 初始化：right = nums.size() - 1。因为区间包含右端点，所以right必须是一个有效的索引。
2. 循环条件：while (left <= right)。当left == right时，区间[left, right]仍然包含一个元素（nums[left]），这是有效的搜索状态，必须进入循环进行检查。只有当left > right（例如left=3, right=2）时，区间才为空，循环终止。
3. 边界更新：因为mid指向的元素在本轮已经被检查过且不等于target，所以在下一轮应该被排除在新搜索区间之外。因此，当目标值在右侧时，新的左边界是mid + 1；在左侧时，新的右边界是mid - 1。更新后的新区间依然是“闭”的。

注意：计算mid时使用left + (right - left) / 2而非(left + right) / 2，是为了防止left和right都很大时相加导致的整数溢出。这是一个非常重要的工程细节。

2.2 左闭右开区间[left, right)

在这种定义下，left指向区间起始（包含），right指向区间终止的下一个位置（不包含）。可以理解为“前闭后开”。

int binarySearch_leftClose(vector<int>& nums, int target) { int left = 0; // 区间左边界，包含 int right = nums.size(); // 区间右边界，不包含！所以初始是数组末尾的下一个位置 while (left < right) { // 关键：当 left == right 时，区间 [left, right) 为空 int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { // 目标在右侧。mid 已检查，新区间为 [mid+1, right) left = mid + 1; } else { // nums[mid] > target // 目标在左侧。mid 已检查，且由于右开，新区间为 [left, mid) // 注意：right 更新为 mid，因为 mid 不包含在新区间内 right = mid; } } // 循环结束，left == right，区间为空，未找到 return -1; }

关键点解析：

1. 初始化：right = nums.size()。因为right是开区间，它指向的是“最后一个元素的下一个位置”，对于长度为n的数组，有效的索引是0到n-1，所以n是一个合法的“开边界”。
2. 循环条件：while (left < right)。当left == right时，区间[left, right)等价于[x, x)，是一个空区间，循环应该终止。如果写成<=，当left == right时，循环还会尝试进入，但此时mid = left，访问nums[mid]可能越界（如果right初始化为nums.size()）或者逻辑混乱。
3. 边界更新：
   • 更新left时依然是mid + 1，因为左闭，新的起点要排除掉已检查的mid。
   • 更新right时是right = mid。因为right是开边界，mid指向的元素在本轮已被检查且应被排除。将right设为mid，意味着新区间是[left, mid)，自然就不包含mid了。这是与“左闭右闭”写法最大的不同。

2.3 左开右闭区间(left, right]

这种写法相对少见，但逻辑是完整的。left指向区间起始的前一个位置（不包含），right指向区间终止（包含）。

int binarySearch_rightClose(vector<int>& nums, int target) { int left = -1; // 区间左边界，不包含！所以初始是第一个索引的前一个位置 int right = nums.size() - 1; // 区间右边界，包含 while (left < right) { // 关键：当 left+1 == right 时，区间 (left, right] 仍有一个元素 // 需要特别处理，避免死循环。通常取上取整中点。 int mid = left + (right - left + 1) / 2; // 向上取整，防止 left 不更新导致的死循环 if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { // 目标在右侧。mid 已检查，新区间为 (mid, right] left = mid; // 因为左开，mid 不包含在新区间内 } else { // nums[mid] > target // 目标在左侧。mid 已检查，新区间为 (left, mid-1] right = mid - 1; } } // 循环结束后，需要检查 right 是否有效且等于 target // 因为循环条件为 left < right，退出时可能 left == right 或 left+1 == right // 更安全的写法是检查 right >= 0 && nums[right] == target if (right >= 0 && nums[right] == target) return right; return -1; }

关键点解析：

1. 初始化：left = -1。因为左开，初始区间(-1, n-1]包含了整个数组。
2. 循环条件与中点计算：这是最容易出错的地方。如果使用mid = left + (right - left) / 2（向下取整），当区间只剩下两个元素(left, right]且nums[mid] < target时，会更新left = mid。由于向下取整，mid可能等于left，导致left没有真正移动，陷入死循环。因此，在左开右闭区间下，通常需要将mid的计算改为向上取整：mid = left + (right - left + 1) / 2。
3. 边界更新：与左闭右开对称，更新left时为left = mid（因为左开），更新right时为right = mid - 1（因为右闭）。
4. 后处理：由于循环条件为left < right，退出时目标值可能就在right指向的位置，需要额外判断。

对比总结：为了更清晰，我们用一个表格来对比三种写法在处理同一数组nums = [1, 2, 3, 4, 5]，查找target = 3时的关键步骤差异（仅展示循环内的逻辑）：

从对比可以看出，左闭右开[left, right)是实践中我个人最推荐的一种。它的初始化right = nums.size()很自然（与 C++ STL 中迭代器end()的理念一致），循环条件left < right清晰，且更新规则对称性好记（小于目标往右缩：left = mid + 1；大于目标往左缩：right = mid）。它避免了左开右闭中关于中点取整的麻烦，也比左闭右闭少一个等号判断（对有些人来说更简洁）。

3. 理解“两段性”：二分查找为何能超越“有序”

我们之前讨论的都是在有序数组中查找一个确定的值。但二分法的威力远不止于此。它的核心思想可以抽象为：在具有两段性的序列上，寻找一个边界。

什么是“两段性”？假设有一个序列，我们可以找到一个条件（或谓词），使得序列可以被这个条件清晰地划分为前后两部分：

• 前半部分的所有元素都不满足该条件。
• 后半部分的所有元素都满足该条件。

那么，这个序列就具有关于该条件的“两段性”。我们的目标，就是找到这个分界点——第一个满足条件的元素的位置，或者最后一个不满足条件的元素的位置。

有序性只是两段性的一个特例。在经典二分查找中，条件P(x)是x >= target。在升序数组中，对于任意位置i，如果nums[i] >= target，那么它之后的所有元素nums[j] (j > i)也一定>= target。因此，序列被分成了“全部< target”和“全部>= target”两段。我们要找的，就是第一个满足P(x)（即>= target）的位置。如果这个位置的值恰好等于target，那就是找到了；如果大于target，说明target不存在。

更广泛的“两段性”应用场景：

1. 寻找峰值：在数组nums中，nums[i] != nums[i+1]。条件P(x)可以是nums[x] > nums[x+1]。对于任意位置i，如果nums[i] > nums[i+1]，那么在i左侧（包含i）可能存在峰值，而i右侧（不包含i）则因为下降趋势，峰值可能在更左边？这里需要更严谨。实际上，我们可以证明，如果nums[mid] > nums[mid+1]，那么峰值一定在[left, mid]区间内；如果nums[mid] < nums[mid+1]，那么峰值一定在[mid+1, right]区间内。这依然构成了两段性。
2. 在旋转排序数组中查找最小值：数组[4,5,6,7,0,1,2]由有序数组旋转得到。条件P(x)可以是nums[x] <= nums[last]（即元素值小于等于最后一个元素）。那么，序列会被分成“大于nums[last]”和“小于等于nums[last]”两段。最小值就在第二段的开头。
3. 二分答案：这是最强大的应用。当问题的答案具有单调性时，我们可以猜测一个答案，然后设计一个检查函数check(mid)来判断这个答案是否“可行”。如果对于某个mid可行，那么所有大于（或小于）mid的答案也可能可行，这就构成了两段性。我们在答案的可能范围内进行二分，寻找最大或最小的可行解。例如，“在D天内运送包裹的能力”、“制作m束花所需的最少天数”等问题。

将区间定义与两段性结合：当我们处理寻找边界的二分问题时，区间定义的选择直接决定了我们找到的是“第一个满足条件的”还是“最后一个不满足条件的”。

以在非降序数组nums中寻找第一个>= target的元素位置为例（即 C++ 中的lower_bound）。

如果我们使用左闭右开[left, right)区间，并定义：

• 循环不变量：[left, right)内始终包含可能的答案（即第一个>= target的位置）。
• 初始化：left = 0,right = nums.size()。答案可能存在于[0, n]（n表示target大于所有元素，应返回n）。
• 循环条件：while (left < right)。当区间不为空时继续。
• 更新逻辑：

  int mid = left + (right - left) / 2; if (nums[mid] >= target) { // mid 满足条件，那么第一个满足条件的位置可能是 mid，也可能在 mid 左边。 // 所以将右边界收缩到 mid（因为右开，新区间是 [left, mid)）。 right = mid; } else { // nums[mid] < target // mid 不满足条件，那么第一个满足条件的位置一定在 mid 右边。 // 所以将左边界收缩到 mid+1。 left = mid + 1; }

• 循环结束：left == right。这个位置就是第一个>= target的元素索引。如果left == n，则表示所有元素都< target。

你会发现，这个写法与之前查找确切值的“左闭右开”模板几乎一样，只是if判断条件从nums[mid] == target变成了nums[mid] >= target，而更新逻辑完全一致。这就是理解了区间定义和两段性后带来的统一性。

实操心得：在处理二分边界问题时，我强烈建议坚持使用同一种区间定义（个人首选[left, right)）。然后，在每次写代码前，花10秒钟明确回答三个问题：

1. 我的搜索区间是什么？（例如：[left, right)代表可能答案的范围）
2. 我的循环不变量是什么？（例如：目标边界一定在当前区间内）
3. 根据mid的判断结果，我该如何更新区间以保持这个不变量？ 回答清楚这三个问题，二分查找的代码就很难写错了。

4. 实战中的典型“坑”与排查心法

即使理解了原理，在实际编码和调试中，依然会遇到一些令人头疼的问题。下面分享几个我踩过的坑以及对应的排查思路。

4.1 死循环：永远跳不出的while

这是二分查找最常见的运行时错误之一。症状是程序在某个测试用例上卡住，超时。

根因分析：死循环几乎总是由于区间收缩不彻底导致的。在while循环中，left和right的更新必须确保搜索区间在每次迭代后都严格变小。如果更新后left或right的值没有变化，或者区间大小不变，就可能陷入无限循环。

典型案例：

1. 在左闭右开[left, right)中，寻找最后一个< target的元素位置（即upper_bound的前一个）。 错误写法可能如下：

   while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid; // 问题在这里！ } else { right = mid - 1; } }

   当nums[mid] < target时，我们知道答案可能在mid或其右侧。但如果令left = mid，考虑区间[left, right)长度为2时，例如left=3, right=5，mid = 4。如果nums[4] < target，则更新left = 4。新区间变为[4, 5)，长度仍然是1（只包含索引4）。下一轮循环，mid再次计算为4（因为(4+5)/2向下取整为4），条件再次满足，left再次被赋值为4……死循环。

   正确更新：当条件满足，我们需要向右搜索时，因为要找的是最后一个满足条件的，mid本身可能是候选，所以不能直接排除。但为了区间收缩，我们应该让left至少移动到mid + 1？不，这可能会跳过正确答案。正确的做法是调整中点取整方向。对于寻找最后一个满足条件A的位置，当条件A(mid)为真时，答案可能在[mid, right)，我们应设置left = mid；为假时，答案在[left, mid)，设置right = mid。但这要求mid的计算向上取整（mid = left + (right - left + 1) / 2），以防止长度为2时的死循环。所以，在左闭右开下，寻找右边界时，常用向上取整的mid。

2. 在左开右闭(left, right]中，使用默认的向下取整计算mid。 如前文所述，这会导致在特定条件下left无法更新。解决方案就是统一在左开右闭写法中使用向上取整。

排查心法：当遇到死循环，第一时间应该检查区间长度为1或2的边界情况。在脑子里模拟，或者用笔在纸上画一下：

• 初始：left = A, right = B。
• 计算mid。
• 根据判断条件，确定left或right如何更新。
• 得到新的left'和right'。
• 检查新区间是否比原区间严格变小（元素个数减少）。如果left' == left且right' == right，或者区间大小不变，死循环就发生了。

4.2 漏解或错解：找不到或找到错误索引

根因分析：这通常是因为区间更新时错误地排除了潜在答案，或者循环结束时没有正确处理剩余的候选。

典型案例：

1. 在左闭右闭[left, right]中，循环条件误写为while (left < right)。 对于数组nums = [5],target = 5。初始left=0, right=0。由于left == right，循环条件left < right为假，直接跳过循环，返回-1，漏掉了唯一可能的解。
2. 在左闭右开[left, right)中，更新right时误写为right = mid - 1。 这会导致当mid就是正确答案时，在下一轮被排除在区间外。例如寻找第一个>= target的位置，nums[mid] >= target时，right应更新为mid以保留mid作为候选。如果写成right = mid - 1，就错了。
3. 在左开右闭(left, right]中，循环结束后忘记对right进行最终判断。 因为循环条件left < right退出时，right指向的位置可能正是答案，需要额外检查。

排查心法：

1. 明确答案的可能范围：在算法开始前，就想清楚答案可能出现在哪些索引。是[0, n-1]还是[0, n]？这决定了left和right的初始值。
2. 维护循环不变量：在每次更新left或right时，问自己：“我这样更新，能保证我要找的答案（如果存在）一定还在新的[left, right)（或[left, right]）区间里吗？” 这是最重要的检查。
3. 测试边界用例：务必用以下用例测试你的二分查找函数（尤其是处理边界问题时）：
   • 空数组。
   • 单元素数组，目标值等于、小于、大于该元素。
   • 双元素数组，目标值分别小于第一个、等于第一个、介于两者之间、等于第二个、大于第二个。
   • 目标值小于数组所有元素。
   • 目标值大于数组所有元素。
   • 数组中有重复元素，查找其左右边界。

4.3 通用调试技巧与模板选择建议

1. 打印日志法：在循环内打印left,right,mid的值以及nums[mid]与target的比较结果。这是最直观的看到算法执行流程和发现问题所在的方法。
2. “闭区间”万能调试起点：如果你不确定用哪种区间定义，可以先从“左闭右闭”[left, right]开始构思。因为它的含义最直观（left和right都是有效索引），循环条件left <= right和更新left = mid + 1/right = mid - 1的逻辑也相对容易推理。在纸上推导无误后，如果需要，再转化为你更习惯的“左闭右开”写法。
3. 固定使用一种风格：我个人的选择是，在绝大多数情况下，统一使用“左闭右开”[left, right)写法。原因如下：
   • 初始化和终止条件自然：right = nums.size()与 C++ 迭代器、Python 切片等概念一致。while (left < right)表示区间非空。
   • 对称性好：更新规则通常是left = mid + 1或right = mid。只需要记住：mid被检查后，如果要排除它，就从新区间里拿掉。因为右边界是开的，所以right = mid正好把mid排除。
   • 便于处理边界：在寻找第一个满足条件的位置（如lower_bound）时，最终返回的left就是答案，且left的范围是[0, n]，完美表示“插入位置”。
4. 理解大于等于/大于的差别：这是实现lower_bound（第一个>= target）和upper_bound（第一个> target）的关键。它们的唯一区别就是if判断条件：

   // lower_bound: 寻找第一个 >= target 的位置 if (nums[mid] >= target) { right = mid; } else { left = mid + 1; } // upper_bound: 寻找第一个 > target 的位置 if (nums[mid] > target) { // 仅此一处不同 right = mid; } else { left = mid + 1; }

   有了lower_bound和upper_bound，查找目标值是否存在、找重复元素的起止范围等问题都迎刃而解。

二分查找的细节就像一把精巧的锁，区间定义和两段性是打开它的两把钥匙。最开始可能会觉得繁琐，但一旦内化，它就会成为一种强大的、近乎本能的解题工具。下次再遇到二分问题，不妨先停下来，花一分钟定义好你的区间和不变量，剩下的就是机械而正确的推导了。