二分查找面试题总结：左右边界、答案二分与 Java 模板

二分查找最容易让人翻车的地方不是思想，而是边界。 、 、 、循环条件、返回值，只要有一个含义没想清楚，就很容易写出死循环或者漏掉答案。 面试里判断能不能用二分，先看一句话： 答案所在空间是否有单调性 。数组有序只是最直观的一种情况，最小速度、最小容量、最小天数这类题，也可以在答案范围上二分。 面试考察重点 能写出基础二分模板。 能处理左边界、右边界。 能识别答案二分，而不是只会在数组里找数。 能解释为什么循环会结束，为什么不会漏答案。 能说出时间复杂度是 ，空间复杂度通常是 。 什么时候想到二分？ 不要把二分查找理解成“只能在有序数组里找数字”。它真正依赖的是 单调性 。 常见单调性有两类： | 类型 | 例子 | 判断方式 | | | | | | 数组单调 | 有序数组中找 | 和 比较后能排除一半 | | 答案单调 | 求最小速度、最小容量、最少天数 | 某个答案可行时，更大的答案也可行，或反过来 | 比如“爱吃香蕉的珂珂”里，吃香蕉速度越快，越容易在规定时间内吃完。这里数组本身不需要有序，单调的是“速度”和“是否能吃完”之间的关系。 面试时可以这样判断： 1. 题目是否在找一个位置、边界或最小/最大可行值？ 2. 如果猜一个答案 ，能不能在 或更低复杂度内判断它是否可行？ 3. 变大或变小时，可行性是否单调变化？ 三个问题都能回答上来，基本就可以尝试二分。 基础二分模板 适合在有序数组中查找一个确定值： 这个模板里，搜索区间是闭区间 ，所以循环条件是 。每次排除 ，因此更新成 或 。 用一句话记这个模板： 区间里每个位置都还可能是答案，循环结束时区间为空。 举个例子，数组 中找 ： 1. ， ， ， ，目标在右侧。 2. 更新 。 3. ，找到 。 如果查找 ，最后会出现 ，说明闭区间已经被排空，返回 。 左边界模板 找第一个大于等于 的位置： 这个模板的搜索区间是左闭右开 。 初始化为 ，返回值可能等于 ，表示数组中不存在大于等于 的位置。 左边界模板的关键不是“找到 target”，而是“找到第一个满足条件的位置”。这个写法能自然处理目标不存在的情况。 比如数组 ，找第一个大于等于 的位置： 当 ， 可能就是答案，所以不能排除 ，更新 。 当 ， 和它左边都不可能是答案，更新 。 循环结束时， ，这个位置就是第一个满足条件的位置。 右边界模板 找最后一个小于等于 的位置，可以先找第一个大于 的位置，再减 1： 这种写法的好处是左右边界只记一套思路：找第一个满足条件的位置。 右边界容易写错，推荐转化成左边界问题： 最后一个小于等于 的位置 = 第一个大于 的位置 1。 最后一个小于 的位置 = 第一个大于等于 的位置 1。 这样不需要维护两套模板，面试手写时更稳。 答案二分 答案二分不是在数组里找元素，而是在答案范围里找最小可行值或最大可行值。 典型问题：给定若干堆香蕉和总时间 ，求最小吃香蕉速度。速度越快，越容易在 小时内吃完，这就是单调性。 这类题通常分两步： 1. 确定答案范围。比如速度最小是 ，最大不超过最大那堆香蕉数。 2. 写 函数。给定一个速度，判断能不能在 小时内吃完。 这个上界成立依赖题目约束： 。因为速度等于最大堆大小时，每堆香蕉最多 1 小时吃完，总耗时不会超过堆数。 这里为什么返回 ？因为循环一直在找“第一个可行速度”。当 为 true，说明 可行，但可能还有更小的速度也可行，所以收缩右边界。最后左右边界重合的位置，就是最小可行速度。 答案二分的 函数往往比二分本身更重要。面试时建议先把 的含义说清楚，再写二分框架。 三类二分怎么选？ | 目标 | 推荐模板 | 返回值 | | | | | | 找到某个等于 的下标 | 基础二分 | 找到返回下标，找不到返回 | | 找第一个满足条件的位置 | 左边界 | 返回 ，可能等于数组长度 | | 找最小可行答案 | 答案二分 | 返回最终的 | 如果题目里有“第一个”“最后一个”“最小可行”“最大可行”，不要急着写基础二分，先判断是不是边界问题。 面试手写路径 二分题的代码不长，面试里更容易被追问的是“你为什么敢丢掉一半”。手写时可以按这个顺序来： 1. 先说明搜索空间：是在数组下标里找，还是在答案范围里找。 2. 再说明单调性： 左右两侧为什么可以排除一边。 3. 明确区间含义：闭区间 还是左闭右开 。 4. 写更新规则： 还能不能成为答案，决定写 还是 。 5. 最后说返回值：循环结束时 、 分别代表什么。 一个很实用的自检问题是： 当 正好满足条件时，我有没有把可能的答案删掉？ 左边界、答案二分里， 经常仍然可能是答案，所以不能随手写成 。 代表题精讲：查找第一个和最后一个位置 34. 在排序数组中查找元素的第一个和最后一个位置 是边界二分的典型题。题目要求返回 的起始和结束位置，如果不存在返回 。 这题不要写成“找到一个 target 后向两边扫描”。虽然能过一些用例，但最坏情况下会退化成 。更稳的写法是做两次边界查找： 第一次找第一个大于等于 的位置。 第二次找第一个大于 的位置，再减 1。 下面两个辅助方法与上文模板一致，这里保留完整代码，方便把返回值含义和主逻辑放在一起对照。 面试里这题常见追问是：如果数组中全是 怎么办？如果 不存在但应该插在中间怎么办？这两个问题其实都在考返回值含义。 返回的是第一个满足条件的位置，不保证这个位置上的值一定等于 ，所以返回前要再检查一次。 过程示意和边界样例 以左边界模板为例，数组 中找第一个大于等于 的位置： | 轮次 | | | | 判断 | 下一步 | | | | | | | | | 1 | 0 | 5 | 2 | | | | 2 | 0 | 2 | 1 | | | | 3 | 0 | 1 | 0 | | | | 结束 | 1 | 1 | | | 返回 1 | 几个边界样例建议手写前先过一遍： | 输入 | 目标 | 预期 | | | | | | | | 返回 或插入位置 ，看题目要求 | | | | 能命中唯一元素 | | | 左边界 | 返回 | | | 左边界 | 返回 | | | 左边界 | 返回 | 常见错误写法： 左边界里，当 时， 仍然可能是答案，所以应该写 。 易错点 可能整数溢出，推荐写成 。 不要混用闭区间和左闭右开区间的更新方式。 找边界时，命中目标后通常不能直接返回，还要继续收缩区间。 答案二分要先证明单调性，不能看到“最小值”就硬套。 这类判断函数里可能需要 ，避免累计值溢出。 高频问题自测 和 有什么区别？ 二分查找为什么是 ？ 找左边界时，为什么命中后要移动 ？ 什么是答案二分？它和普通二分有什么区别？ 二分查找一定要求数组有序吗？ 推荐练习题 704. 二分查找 35. 搜索插入位置 34. 在排序数组中查找元素的第一个和最后一个位置 875. 爱吃香蕉的珂珂 1011. 在 D 天内送达包裹的能力 写在最后 如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。 JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。 如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。