前阵子帮人做代码评审看到一段二分查找循环条件写的while (left right)区间却用的左闭右闭数组只有一个元素时直接漏判——这个 bug 在单测里基本测不出来因为大部分测试数据都是长数组。类似的问题我几乎每次带新人都会遇到所以今天专门把 Java 二分查找这块的循环条件和区间写法掰开揉碎讲一遍顺带把三种主流写法、四个高频变体和我在实战里踩过的坑都整理出来。不管你是准备面试还是刷题看完应该不会再被left、right的边界问题难住。1. 死循环第一次出现left mid 的翻车现场先说一个我印象非常深刻的错误版本。当时是一个工作了两年的 Java 同学写的逻辑看起来完全没毛病// 这段代码会死循环仅供分析不要在生产环境运行 int wrongBinarySearch(int[] nums, int target) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid; // 问题出在这里 } else { right mid; } } return nums[left] target ? left : -1; }初看确实没什么问题mid 比 target 小就把左边界挪过来否则把右边界挪过来最后 left 和 right 会收敛到同一个位置再判断这个位置是不是 target。问题出在区间长度只剩 2 的时候。假设 left 4、right 5那么 mid 4 (5 - 4) / 2 4mid 取到了左端点。如果 nums[4] target进入left mid分支后left 还是 4下一轮循环的 mid 还是 4条件是left right依旧成立——代码就卡在这一轮里无限循环。这就是二分查找死循环的经典触发条件mid 向下取整拿到了左端点而分支里又把 left 原地赋回去区间一个元素都没淘汰。后来我把这个教训简化成两条铁律写进自己的代码规范里如果 mid 取下整mid left (right - left) / 2那么 left 绝对不能等于 mid至少要写成left mid 1。如果某个分支确实需要保留 mid也就是写left mid那 mid 必须向上取整写成mid left (right - left 1) / 2保证 left 能真正越过 mid 前进。为什么这两条规则能防死循环因为二分查找本质上就是每轮淘汰一批元素如果某轮一个元素都没淘汰循环条件永远成立死循环就必然出现。你不需要把各种边界情况都背下来只要抓住区间必须缩小这一条很多坑都能提前避开。2. 区间写法的底层逻辑不变量决定一切很多教程把二分查找讲成猜数字游戏这确实形象但也容易让人产生一个错觉我只要不停取中点、比较、缩范围就行。真正动手写代码的时候问题就变成猜完之后下一轮到底该查哪些数而这就是区间写法要解决的问题。我的建议是写二分查找之前先别急着敲 while先在脑子里回答三个问题当前可能包含答案的区间我定义成闭区间还是开区间循环开始前区间外的元素处于什么状态哪些已经确定不是答案某次比较之后区间怎么缩才能让第 1、2 条保持不变这三个问题想清楚循环条件和边界更新自然就有了不需要硬背。2.1 左闭右闭 [left, right]教科书写法与它的隐患左闭右闭是 Java 教材里出现频率最高的写法left 0right nums.length - 1区间内的每一个下标都可能是答案。循环条件必须写while (left right)。为什么呢因为当 left right 时区间里还剩最后一个元素它依然可能是 target。如果你写成left right这个最后元素就被排除了循环结束之后还得额外判断逻辑上会出现漏洞。对应的更新规则也很明确如果nums[mid] target说明 mid 以及它左边的元素都比 target 小不可能再是答案左边界直接越过 midleft mid 1。如果nums[mid] target说明 mid 以及它右边的元素都比 target 大不可能再是答案右边界直接越过 midright mid - 1。左闭右闭最直观但它有个现实中的隐患——当你用它实现找第一个大于等于 target 的位置时会非常别扭。因为右端点天生被限制在 n - 1 上如果所有元素都比 target 小区间缩到只剩最后一个元素就停住了你必须写一段额外的判断来返回数组长度 n。这一点我在第 4 节的模板里会具体演示。2.2 左闭右开 [left, right)我更推荐的日常写法左闭右开的核心约定只有一条right 指向的元素永远不包含在待搜索区间里。正是因为 right 是一个不包括的端点初始值可以直接取nums.length哪怕数组为空、或者所有元素都小于 target这个区间也都装得下答案不需要任何特殊处理。循环条件写while (left right)因为当 left right 时区间长度为 0没有任何元素可查。更新规则也有细微变化如果nums[mid] targetleft mid 1。如果nums[mid] targetright mid而不是right mid - 1。这里right mid很多新手不理解会觉得既然 nums[mid] 已经大于 target 了为什么不把它也排除掉答案就在那条约定里right 指向的元素本来就不在区间内。把 mid 这个已经确定大于 target的元素留在区间右边就是把它从区间里剔除。如果你写成 right mid - 1反而会把区间切开丢失一部分候选元素。死循环在这套写法里很难触发left mid 1 和 right mid 都会让区间长度严格变小不存在原地踏步的分支。2.3 左开右开 (left, right)哨兵模型帮你彻底想通边界第三种写法日常用得少但它特别适合用来理解二分查找的本质也适合在面试被追问时拿出来展示深度。我称之为哨兵写法// 左开右开 (left, right)left 和 right 是虚拟哨兵 int lowerBoundOpen(int[] nums, int target) { int left -1, right nums.length; while (left 1 right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid; } else { right mid; } } return right; }这里的 -1 和 nums.length 是两个虚拟哨兵初始区间是(-1, nums.length)不代表任何真实元素。循环条件left 1 right表达的是left 和 right 之间还隔着至少一个真实元素。这样写的好处是两个边界更新都可以放心用left mid或者right mid因为当 left 和 right 相邻时循环就结束了mid 落在端点上也不会造成死循环。整个搜索维护的不变量是left 永远指向确定比 target 小的位置right 永远指向不确定或者确定不小于 target的位置。结束时 left 1 rightright 就是第一个 target 的下标。代价也很明显哨兵位置不能直接访问 nums[-1] 和 nums[nums.length]循环结束后再去拿 left 或 right 访问数组就会越界。它更像一个用来推演边界的理想模型工程代码里我更倾向用左闭右开但理解这个模型对突破边界困惑非常有帮助。3. 三种区间写法的对照表循环条件与更新规则一次对齐我平时会把三种区间写法整理成一张对照表每次写二分查找前先确定自己用的是哪一行再动手。这张表已经存进我自己的知识库很久了区间语义初始值循环条件mid 取整nums[mid] target时其他情况结束时 left / right 状态左闭右闭 [left, right]left0, rightn-1left right下取整left mid 1right mid - 1left right 1答案可能不存在左闭右开 [left, right)left0, rightnleft right下取整left mid 1right midleft right直接就是下界左开右开 (left, right)left-1, rightnleft 1 right下取整left midright midleft 1 rightright 是下界这张表最值得记的其实是两件事循环条件取决于区间是否包含端点更新规则取决于右端点是否真的在区间内。只要这两点对应上换用哪种区间写法都不会出原则性错误。3.1 写 mid 时Java 开发者最容易忽略的溢出这里有一个 Java 专属细节。mid (left right) / 2在绝大多数真实环境下不会出错因为数组长度往往远小于 int 的最大值。但(left right)一旦超过 2147483647加法会溢出成负数mid 变成负数之后访问数组直接抛 ArrayIndexOutOfBoundsException。虽然二十亿规模的数据不常见但left (right - left) / 2这个写法成本为零、收益为正属于典型的靠一行代码消除隐患。需要向上取整时写成left (right - left 1) / 2也一样顺手规避溢出。3.2 循环条件的等价转化left right 和 left right 差在哪很多人靠死记左闭右闭用 左闭右开用 但被问一句背反了会怎样就懵了。其实用一条数轴就能解释清楚。假设 left 2、right 3如果是左闭右闭区间内包含下标 2 和 3 两个元素。此时循环条件写left right循环体一结束下标 3 就成了漏网之鱼。反过来如果是左闭右开right 本来就不包含元素left right精确表达区间长度 0加不加等号区别不大但写成left right会让语义变得含混有些场景下会出现区间永不空的退化。这些等价关系不需要背它只是区间定义的数学表达。你能说出当前区间里还剩哪些元素时循环条件就是一眼的事。4. 四大高频场景模板查找、下界、上界、插入位置二分查找在实际项目里很少只用来找一个等于 target 的下标。绝大多数需求是这四种精确查找、第一个 targetlowerBound、第一个 targetupperBound、以及插入位置。下面我统一用左闭右开给完整模板因为它不需要后处理边界逻辑最干净。4.1 精确查找命中即返回public int binarySearch(int[] nums, int target) { int left 0, right nums.length; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid; } } return -1; }这个模板在力扣 704 上反复验证过空数组、单个元素、重复元素都没问题。注意它一旦命中就直接 return中断循环所以只适合返回任意一个相等下标的场景。要是数组里有重复元素而且你要的是第一个等于 target 的下标或等于 target 的个数就得用 next 这一节的 lowerBound。4.2 lowerBound第一个 target 的位置// 返回第一个满足 nums[i] target 的下标范围在 [0, nums.length] 内 public int lowerBound(int[] nums, int target) { int left 0, right nums.length; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }这套代码维护的不变量是[0, left)里的元素全部小于 target[right, n)里的元素全部大于等于 target。因为只有两个分支等于 target 的情况被自动归入else驱动 right 不断往左缩所以它找的必然是第一个等于或大于 target 的位置。lowerBound 的返回值天然覆盖所有边界全部小于 target 时返回 nums.length全部大于等于 target 时返回 0不用任何后处理。这是左闭右开写法最香的地方。4.3 upperBound第一个 target 的位置// 返回第一个满足 nums[i] target 的下标范围在 [0, nums.length] 内 public int upperBound(int[] nums, int target) { int left 0, right nums.length; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }对比 lowerBound 只改了一个符号比较条件从变成。这个改动的含义是等于 target 的元素不再被保留在右半区间left 会推进到它们后面去找第一个严格大于 target 的位置。因此upperBound(target) - 1正好是最后一个等于 target 的元素的下标。还有个等价关系可以顺手记住upperBound(target) lowerBound(target 1)。原因很简单第一个大于 target 的整数位置等同于第一个大于等于 target1 的位置。在整数数组的场景下这个转换非常常用。4.4 插入位置与左右边界力扣 35 的思路力扣 35 题Search Insert Position求的就是 lowerBound。给定有序数组和 target返回 target 插入后依然有序的下标直接用上面的 lowerBound 模板即可nums [1,3,5,6]target 5返回 2。target 2返回 1插在 1 和 3 之间。target 7返回 4插到末尾。target 0返回 0插到头部。四个典型场景全被 lowerBound 的自然语义覆盖不用额外写 if。这就是区间不变量设计得好带来的红利你想到的是插入位置代码表达的是第一个 target 的位置两者在数学上完全等价。顺便对比一下左闭右闭版的 lowerBound方便你看清它的后处理问题public int lowerBoundClosed(int[] nums, int target) { if (nums.length 0) return 0; int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return nums[left] target ? left : left 1; }这段代码在 target 大于数组所有元素时循环结束后 left right n - 1但 nums[left] target所以必须返回 left 1 才等于 n。每次写左闭右闭版 lowerBound 都要多考虑这一个 corner case写多了很容易漏这也是我日常默认左闭右开的原因之一。5. 面试与工程里的高频坑边界、空数组、死循环排错最后这部分与其说是知识点不如说是事故记录。这些年我自己踩过、也帮别人 review 出过不少二分问题集中列出来每一个都对应真实案例。5.1 左闭右闭 while (left right) 的组合漏判新手最常见的问题想用左闭右闭却套了左闭右开的循环条件。当数组只有一个元素时比如 nums [5], target 5区间 [0, 0] 里明明有答案但left right不成立循环一次都不执行直接返回 -1。这种 bug 在单元测试里特别容易漏因为测试数据往往是长数组没人专门测单元素。我建议写二分时先把区间定义写出来再对应写循环条件。如果你自己都说不清 left right 时区间里还剩没剩元素那大概率会在这里翻车。5.2 空数组与循环结束后的访问左闭右开写法面对空数组非常舒服nums.length 0 时 left 0、right 0while 条件立刻不满足直接走到 return永远不会访问 nums[mid]。不需要单独写 if这就是right 不包含端点带来的额外好处。真正容易炸的是那种循环结束后直接访问 nums[left] 的版本比如我开头那个错误代码。空数组下 nums[0] 并不存在但因为下标 0 合法编译器不报错运行起来才抛异常。如果你在刷题平台或者 PTA 上遇到过诡异的内存访问错误先排查一下是不是二分结束后拿了 left 去访问数组。5.3 mid 取整方向与 left mid 的死循环配对再重述一遍死循环配对规则这次给完整版本如果写left mid且 mid 是向下取整得到的区间长度为 2 时 mid leftleft 原地不动死循环。解决办法要么让 mid 向上取整要么把左边界改成left mid 1。我个人的可读性偏好是能left mid 1就不left mid因为向上取整会让代码阅读者困惑。只有在必须保留 mid比如找左边界时需要保留等于 target 的元素继续往左压缩的场景才配合左开右开模型解决。5.4 面试官最爱追问的四个点面试时写二分查找大概率被追问下面这几个问题建议提前想清楚返回 left 还是 right左闭右开结束时 left right返回谁都一样左开右开结束时 left 1 right必须返回 right因为 left 可能落在一个小于 target的位置上。这条循环的不变量是什么能答出区间内全是候选区间外全是淘汰这个级别的答案基本就过关了。数组有大量重复元素时模板还能找到第一个吗能因为等于 target 的分支同样走 right mid天然往左压缩。如果我想找最后一个小于 target 的元素呢等价于lowerBound(target) - 1前提是结果不低于 0。低于 0 就代表不存在。5.5 我的个人默认套路说了这么多最后分享我自己的固定习惯你完全可以照搬默认用左闭右开 [left, right)循环条件while (left right)mid 一律left (right - left) / 2。比较逻辑只保留一个二元分支if (nums[mid] target) left mid 1; else right mid;。等于的情况被 else 天然吸收这就是 lowerBound 的统一骨架。需要精确查找时在骨架上加一个命中判断需要上界时把改成需要统计左右边界时直接用 upperBound 减 lowerBound 就能算出区间长度。这个套路让我在刷题时遇到所有二分题都能快速进入套骨架 改一个条件的流程。二分查找的代码量就那么十几行真正值钱的是你脑子里那张区间状态表。最后再分享一个实战排错小技巧如果发现自己的二分查找异常卡顿十有八九是死循环不要急着打断点。先在纸上写出当前区间定义、循环条件和两个更新语句然后拿 left2、right3 这种长度为 2 的场景手推一轮。你会很快看出 mid 取整方向到底跟哪个分支冲突。这个方法我帮同事排查过至少三次每次都能在五分钟内定位问题比盲目加日志快得多。