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(vectorint 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 已经检查过且不是所以新区间从 mid1 开始 left mid 1; } else { // nums[mid] target // 目标在左侧mid 已经检查过且不是所以新区间到 mid-1 结束 right mid - 1; } } // 循环结束说明 left right区间为空未找到 return -1; }关键点解析初始化right nums.size() - 1。因为区间包含右端点所以right必须是一个有效的索引。循环条件while (left right)。当left right时区间[left, right]仍然包含一个元素nums[left]这是有效的搜索状态必须进入循环进行检查。只有当left right例如left3, right2时区间才为空循环终止。边界更新因为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(vectorint 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 已检查新区间为 [mid1, right) left mid 1; } else { // nums[mid] target // 目标在左侧。mid 已检查且由于右开新区间为 [left, mid) // 注意right 更新为 mid因为 mid 不包含在新区间内 right mid; } } // 循环结束left right区间为空未找到 return -1; }关键点解析初始化right nums.size()。因为right是开区间它指向的是“最后一个元素的下一个位置”对于长度为n的数组有效的索引是0到n-1所以n是一个合法的“开边界”。循环条件while (left right)。当left right时区间[left, right)等价于[x, x)是一个空区间循环应该终止。如果写成当left right时循环还会尝试进入但此时mid left访问nums[mid]可能越界如果right初始化为nums.size()或者逻辑混乱。边界更新更新left时依然是mid 1因为左闭新的起点要排除掉已检查的mid。更新right时是right mid。因为right是开边界mid指向的元素在本轮已被检查且应被排除。将right设为mid意味着新区间是[left, mid)自然就不包含mid了。这是与“左闭右闭”写法最大的不同。2.3 左开右闭区间(left, right]这种写法相对少见但逻辑是完整的。left指向区间起始的前一个位置不包含right指向区间终止包含。int binarySearch_rightClose(vectorint nums, int target) { int left -1; // 区间左边界不包含所以初始是第一个索引的前一个位置 int right nums.size() - 1; // 区间右边界包含 while (left right) { // 关键当 left1 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 或 left1 right // 更安全的写法是检查 right 0 nums[right] target if (right 0 nums[right] target) return right; return -1; }关键点解析初始化left -1。因为左开初始区间(-1, n-1]包含了整个数组。循环条件与中点计算这是最容易出错的地方。如果使用mid left (right - left) / 2向下取整当区间只剩下两个元素(left, right]且nums[mid] target时会更新left mid。由于向下取整mid可能等于left导致left没有真正移动陷入死循环。因此在左开右闭区间下通常需要将mid的计算改为向上取整mid left (right - left 1) / 2。边界更新与左闭右开对称更新left时为left mid因为左开更新right时为right mid - 1因为右闭。后处理由于循环条件为left right退出时目标值可能就在right指向的位置需要额外判断。对比总结为了更清晰我们用一个表格来对比三种写法在处理同一数组nums [1, 2, 3, 4, 5]查找target 3时的关键步骤差异仅展示循环内的逻辑步骤左闭右闭[l, r]左闭右开[l, r)左开右闭(l, r]初始化l0, r4l0, r5l-1, r4循环条件l rl rl r第一轮mid2,nums[2]3找到。mid2,nums[2]3找到。mid2(上取整),nums[2]3找到。若查找target2第一轮mid2,nums[2]32,r1。第二轮l0,r1,mid0,nums[0]12,l1。第三轮l1,r1,mid1,nums[1]2找到。第一轮mid2,nums[2]32,r2。第二轮l0,r2,mid1,nums[1]2找到。第一轮mid2,nums[2]32,r1。第二轮l-1,r1,mid0(上取整),nums[0]12,l0。第三轮l0,r1,mid1(上取整),nums[1]2找到。更新规则l mid 1r mid - 1l mid 1r midl midr mid - 1中点取整通常向下取整通常向下取整通常向上取整防死循环从对比可以看出左闭右开[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不存在。更广泛的“两段性”应用场景寻找峰值在数组nums中nums[i] ! nums[i1]。条件P(x)可以是nums[x] nums[x1]。对于任意位置i如果nums[i] nums[i1]那么在i左侧包含i可能存在峰值而i右侧不包含i则因为下降趋势峰值可能在更左边这里需要更严谨。实际上我们可以证明如果nums[mid] nums[mid1]那么峰值一定在[left, mid]区间内如果nums[mid] nums[mid1]那么峰值一定在[mid1, right]区间内。这依然构成了两段性。在旋转排序数组中查找最小值数组[4,5,6,7,0,1,2]由有序数组旋转得到。条件P(x)可以是nums[x] nums[last]即元素值小于等于最后一个元素。那么序列会被分成“大于nums[last]”和“小于等于nums[last]”两段。最小值就在第二段的开头。二分答案这是最强大的应用。当问题的答案具有单调性时我们可以猜测一个答案然后设计一个检查函数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 右边。 // 所以将左边界收缩到 mid1。 left mid 1; }循环结束left right。这个位置就是第一个 target的元素索引。如果left n则表示所有元素都 target。你会发现这个写法与之前查找确切值的“左闭右开”模板几乎一样只是if判断条件从nums[mid] target变成了nums[mid] target而更新逻辑完全一致。这就是理解了区间定义和两段性后带来的统一性。实操心得在处理二分边界问题时我强烈建议坚持使用同一种区间定义个人首选[left, right)。然后在每次写代码前花10秒钟明确回答三个问题我的搜索区间是什么例如[left, right)代表可能答案的范围我的循环不变量是什么例如目标边界一定在当前区间内根据mid的判断结果我该如何更新区间以保持这个不变量 回答清楚这三个问题二分查找的代码就很难写错了。4. 实战中的典型“坑”与排查心法即使理解了原理在实际编码和调试中依然会遇到一些令人头疼的问题。下面分享几个我踩过的坑以及对应的排查思路。4.1 死循环永远跳不出的while这是二分查找最常见的运行时错误之一。症状是程序在某个测试用例上卡住超时。根因分析死循环几乎总是由于区间收缩不彻底导致的。在while循环中left和right的更新必须确保搜索区间在每次迭代后都严格变小。如果更新后left或right的值没有变化或者区间大小不变就可能陷入无限循环。典型案例在左闭右开[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时例如left3, right5mid 4。如果nums[4] target则更新left 4。新区间变为[4, 5)长度仍然是1只包含索引4。下一轮循环mid再次计算为4因为(45)/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。在左开右闭(left, right]中使用默认的向下取整计算mid。 如前文所述这会导致在特定条件下left无法更新。解决方案就是统一在左开右闭写法中使用向上取整。排查心法当遇到死循环第一时间应该检查区间长度为1或2的边界情况。在脑子里模拟或者用笔在纸上画一下初始left A, right B。计算mid。根据判断条件确定left或right如何更新。得到新的left和right。检查新区间是否比原区间严格变小元素个数减少。如果left left且right right或者区间大小不变死循环就发生了。4.2 漏解或错解找不到或找到错误索引根因分析这通常是因为区间更新时错误地排除了潜在答案或者循环结束时没有正确处理剩余的候选。典型案例在左闭右闭[left, right]中循环条件误写为while (left right)。 对于数组nums [5],target 5。初始left0, right0。由于left right循环条件left right为假直接跳过循环返回-1漏掉了唯一可能的解。在左闭右开[left, right)中更新right时误写为right mid - 1。 这会导致当mid就是正确答案时在下一轮被排除在区间外。例如寻找第一个 target的位置nums[mid] target时right应更新为mid以保留mid作为候选。如果写成right mid - 1就错了。在左开右闭(left, right]中循环结束后忘记对right进行最终判断。 因为循环条件left right退出时right指向的位置可能正是答案需要额外检查。排查心法明确答案的可能范围在算法开始前就想清楚答案可能出现在哪些索引。是[0, n-1]还是[0, n]这决定了left和right的初始值。维护循环不变量在每次更新left或right时问自己“我这样更新能保证我要找的答案如果存在一定还在新的[left, right)或[left, right]区间里吗” 这是最重要的检查。测试边界用例务必用以下用例测试你的二分查找函数尤其是处理边界问题时空数组。单元素数组目标值等于、小于、大于该元素。双元素数组目标值分别小于第一个、等于第一个、介于两者之间、等于第二个、大于第二个。目标值小于数组所有元素。目标值大于数组所有元素。数组中有重复元素查找其左右边界。4.3 通用调试技巧与模板选择建议打印日志法在循环内打印left,right,mid的值以及nums[mid]与target的比较结果。这是最直观的看到算法执行流程和发现问题所在的方法。“闭区间”万能调试起点如果你不确定用哪种区间定义可以先从“左闭右闭”[left, right]开始构思。因为它的含义最直观left和right都是有效索引循环条件left right和更新left mid 1/right mid - 1的逻辑也相对容易推理。在纸上推导无误后如果需要再转化为你更习惯的“左闭右开”写法。固定使用一种风格我个人的选择是在绝大多数情况下统一使用“左闭右开”[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]完美表示“插入位置”。理解大于等于/大于的差别这是实现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查找目标值是否存在、找重复元素的起止范围等问题都迎刃而解。二分查找的细节就像一把精巧的锁区间定义和两段性是打开它的两把钥匙。最开始可能会觉得繁琐但一旦内化它就会成为一种强大的、近乎本能的解题工具。下次再遇到二分问题不妨先停下来花一分钟定义好你的区间和不变量剩下的就是机械而正确的推导了。