二分查找边界与快排partition：面试算法核心拆解

前阵子一个准备跳槽的朋友跟我聊天，说他把牛客面试 TOP 101 刷了两轮，特别是二分查找和排序这块，题目都背得滚瓜烂熟了，结果模拟面试时一上手手写二分，还是在边界条件上卡了壳。这其实不是个例。很多人在 LeetCode 和牛客上刷了上百题，但真到了面试那种无 IDE、有面试官盯着的环境下，容易暴露一个核心问题：只知道模板，不知道模板为什么长这样，更不知道哪些场景该换哪一种写法。

这篇就是针对牛客面试 TOP 101 二分查找/排序篇（二）的深入拆解。我不想再贴一遍基础模板然后说"多刷几道就会了"，而是把这一组题目背后最关键的几个分水岭问题——二分边界怎么写不死循环、快排 partition 怎么才能顺手写出 TopK、以及二分和排序组合在一起的综合题该怎么拆——都摊开来讲清楚。适合正在集中刷算法题准备面试的人，也适合刷完基础题但总在细节上丢分的同学。

1. 二分查找的"左右为难"：边界条件的实操拆解

1.1 为什么面试官总爱问 left < right 还是 left <= right

二分查找是所有算法面试题里最容易被低估的一类。看起来代码就十行，可考察的细节密度极高：while 条件怎么写，left 和 right 的初始值是什么，mid 取左中位还是右中位，更新区间时是 mid 还是 mid + 1 / mid - 1。这些变量组合在一起，能凑出十几种写法，而其中一半会死循环或漏答案。

面试官不是真的在乎你默认用哪种写法，而是想观察两件事：第一，你是否理解循环不变量的含义——你定义的 left/right 区间是闭区间还是开区间，决定了下一次缩小区间时要不要跳过 mid；第二，你在边界情况下（数组长度 1、目标值在两端、目标值不存在）是否还能保持代码正确。

我在牛客刷二分题时有个体会：很多题解里会看到 left <= right 和 left < right 两种风格，初学者经常混着用。一旦混用，最常见的结果就是死循环。举个例子，如果你用 left < right 作为循环条件，但在更新时写 left = mid，而 mid 取的是左中位（向下取整），那么当 left 和 right 相邻时，mid 永远等于 left，区间永不缩小，程序就在那里空转。

这就是为什么理解"循环不变量"比背模板重要。我后面会给一套我认为最稳妥的写法，但你先得明白：鲁棒性的根源在于每一步都在缩减搜索区间，并且保证目标值始终留在区间内。

1.2 三种常见写法的适用场景和死循环风险

先说说我在各种面经和题解里见过的三种主流风格。

第一种：闭区间写法，while (left <= right)。

这种写法把 left 和 right 都看作是包含目标的区间端点。每次比较过后，如果目标值在左侧，就 right = mid - 1，在右侧就 left = mid + 1。因为当 left == right 时，这个位置的元素还没有被判断过，所以要继续循环，直到 left > right 才停止。

它不会死循环，因为无论哪种分支，left 或 right 都会跨过 mid，区间长度必然递减。比较适合在标准数组中找精确值。

第二种：左闭右开写法，while (left < right)。

这里 right 表示的是一个"取不到的边界"，所以循环结束后 left 会收敛到右边界。因为 left < right 时，若取左中位 mid，且更新为 left = mid，确实可能卡住。因此很多实现会刻意让二分查找左边界时配合 right = mid 这种缩减方式。它用于找左边界/右边界时很顺手，但如果你不理解"右侧是开区间"，容易写出死循环。

第三种：暴力退出写法，while (left + 1 < right)。

这种写法在 left 和 right 距离小于等于 1 时退出，最后用两个候选位置做后处理，检查 left 和 right 是否满足条件。它的好处是 mid 不管怎么取都不会死循环，因为最后区间里至少还有一个元素，你可以写一个 helper 函数直接判断。代价是返回值需要多做两个 if 判断。

没有哪一种写法是绝对"正确"的，重要的是在同一个程序里守住一种语义。面试时我会建议你用你最熟悉的那一种，但前提是你能把它的边界条件讲明白。

1.3 一个可以直接背下来的安全模板

我不太主张完全背模板，但如果要我推荐一套对所有二分变体都比较安全的写法，我会选择"开区间 + 后处理"的思路。这套写法的好处是，把"边界到底包不包含"的纠结延后到循环结束，循环体内只需要做常规的比较移动。

下面以"在升序数组中找目标值，存在返回下标，不存在返回 -1"为例：

public int binarySearch(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int left = 0, right = nums.length - 1; while (left + 1 < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid; } else if (nums[mid] > target) { right = mid; } else { return mid; } } if (nums[left] == target) { return left; } if (nums[right] == target) { return right; } return -1; }

这份代码里有两个关键点：

• mid = left + (right - left) / 2而不是(left + right) / 2，是为了防止整形溢出。面试时如果数组长度接近Integer.MAX_VALUE，直接相加会溢成负数，这是个很经典的暗坑。
• 循环条件left + 1 < right保证循环终止时 left 和 right 至少相邻，循环内 left 和 right 每次都会更新到 mid 位置，所以不会死循环。循环结束后再做两个判断，把"最后一个可能的位置"也覆盖到。

如果你背这个模板，面试时一定要记得解释：为什么要后处理两个位置？因为当数组只剩两个元素时（left 和 right 紧挨着），循环就退出了，这两个元素都有可能是目标值，所以要在循环后检查。这种解释比单纯说"这是左闭右开"更能体现你懂原理。

1.4 常见问题：求左侧边界、右侧边界、第一个不小于目标值的位置

牛客的二分题很少直接让你找精确值，更多是找边界。我整理了几个高频变体。

问题 A：找目标值第一次出现的下标（左侧边界）。如果直接用上面模板，nums[mid] == target时不能马上返回，因为左边可能还有等于 target 的值。这时候应该收缩右边界：if (nums[mid] >= target) { right = mid; }，继续往左找。循环结束后先检查 left，再检查 right，但注意要取更靠左的那个有效值。

问题 B：找目标值最后一次出现的下标（右侧边界）。和 A 相反，当nums[mid] <= target时收缩左边界：left = mid。同时为了避免死循环，这种场景下 mid 建议取右中位mid = left + (right - left + 1) / 2，否则又会遇到 left 卡住的问题。

问题 C：找第一个不小于 target 的位置（lower_bound）。这是 C++ 里lower_bound的语义。可以用while (left < right)加右移 left 的思路，也可以用上面的后处理模板，最后找一个既大于等于 target、下标又最小的元素。这个能力在"在排序数组中查找元素的第一个和最后一个位置"这类题里直接用到。

我建议你把这些变体写在同一个代码文件里，分别跑几组测试数据，尤其要测数组长度为 1、目标值不在数组内、目标值比所有元素都大/小这几种情况。面试前把边界测试用例自己过一遍，比多刷十道题都有用。

2. 排序算法不只是背代码：快排 partition 才是真正的分水岭

2.1 快排和归并的考察差异

二分和排序常放在同一个专题里，因为很多面试题不是单纯让你排序，而是在排序过程中完成某种统计，或者利用排序后的有序性质解决其他问题。而在排序算法本身，面试官问得最多的就是快排和归并。

你会发现快排的代码所有人都会背，但真到现场让写一个稳定的快排、或者分析最坏情况复杂度，很多人就开始支支吾吾。原因在于：大家背的是"主函数递归调用 partition"，但忘了 partition 本身是一个可以独立出题的核心函数。归并排序则常和逆序对绑定在一起，考察你对"合并过程中是否能利用有序性做额外计算"的理解。

另外，面试官问"排序算法是否稳定"时，本质上是在考察你是否清楚元素相等时相对顺序是否会被改变。快排如果实现得不好就不稳定，归并排序是稳定的。很多高级场景，比如按多个字段排序，稳定性就很重要。

2.2 partition 函数的三种写法

我第一次准备面试时以为 partition 就是来回交换，后来发现写法有区别，而且面试官喜欢顺着你的写法追问。

写法一：单向扫描。

private int partition(int[] nums, int low, int high) { int pivot = nums[high]; int i = low; for (int j = low; j < high; j++) { if (nums[j] < pivot) { swap(nums, i, j); i++; } } swap(nums, i, high); return i; }

这种写法从左到右扫一遍，遇到比 pivot 小的就往前放。它的优点是直观，缺点是对重复元素的处理不够好，而且会把相等的元素随意分配到两侧，所以不稳定。

写法二：双向扫描（霍尔分区）。

private int partition(int[] nums, int low, int high) { int pivot = nums[low]; int i = low, j = high; while (i < j) { while (i < j && nums[j] >= pivot) j--; nums[i] = nums[j]; while (i < j && nums[i] <= pivot) i++; nums[j] = nums[i]; } nums[i] = pivot; return i; }

这个写法的好处是原地覆盖，额外空间少。但它有一个很隐蔽的坑：nums[j] >= pivot和nums[i] <= pivot里的等号不能随便去掉。去掉以后遇到大量重复元素时，指针会停在中途互相"打架"，甚至越界。面试时你能主动提到这点，会非常加分。

写法三：三路快排 partition。

当数组里重复元素很多时，普通快排会退化到 O(n²)。三路快排把数组分成< pivot、== pivot、> pivot三部分，递归时只处理左右两部分，中间相等部分直接跳过。Java 的Arrays.sort()对对象排序时也用了类似思想（TimSort 和 DualPivotQuicksort）。

三路快排的核心不再是一个 partition 函数，而是一个循环：

private void quickSort3(int[] nums, int low, int high) { if (low >= high) return; int pivot = nums[low + (high - low) / 2]; int lt = low, i = low, gt = high; while (i <= gt) { if (nums[i] < pivot) { swap(nums, lt++, i++); } else if (nums[i] > pivot) { swap(nums, i, gt--); } else { i++; } } quickSort3(nums, low, lt - 1); quickSort3(nums, gt + 1, high); }

看到这段代码，面试官如果问"为什么 i 不动？"你要能答出：因为从 gt 交换过来的数还没有被比较过，所以 i 不能直接前进，需要再检查一次。这种细节最容易体现你是真的理解而不是背代码。

2.3 从快速排序到 TopK 问题：经典题目的现场推演

快排的价值不止于排序。面试里大名鼎鼎的"数组中的第 K 个最大元素"，最快解法就是基于 partition 的减治思路，而不是完整排序。

我在牛客的题目页里经常看到有人直接Arrays.sort()然后取下标，这样虽然能过笔试，但面试时如果你这么回答，面试官通常会追问："如果不允许用现成排序，或者数组非常大怎么办？"

正确思路是：利用 partition 之后，pivot 所在的位置就是它最终排好序后的位置，并且左侧元素都小于等于它、右侧元素都大于等于它。所以只要看 pivot 的位置和 K 的关系：

• 如果要找第 K 大（即升序后的第 n-K 个元素），当 pivot 的下标 == n-K，直接返回；
• 如果 pivot 的下标 < n-K，说明第 K 大在右半部分，递归/循环处理右半边；
• 如果大于，则处理左半边。

平均复杂度 O(n)，最坏 O(n²)。为了避免最坏情况，可以随机选择 pivot。这也是一个加分点，你可以说自己会用swap(nums, low, low + random.nextInt(high - low + 1))来随机化。

实际现场推演时，我建议你写一个循环而不是递归的版本，因为循环更容易控制边界，也不容易栈溢出。面试官看到你能写出非递归版本，通常会对你的代码功底有更高评价。

2.4 三路快排解决重复元素场景

回到三路快排，它在面试中出现的原因还有一个：很多排序相关的变形题，比如"荷兰国旗问题"，本质上就是一次三路 partition。

荷兰国旗问题要求把数组分成三段：小于目标值、等于目标值、大于目标值。你直接用上面的三路快排中的循环即可。面试时如果先让你写三路快排，再让你做荷兰国旗，你可以直接说"这个问题就是三路快排的核心逻辑"，然后写出代码，几乎是无缝衔接。

我自己的经验是：不要学十种排序，把快排学透，就够应对绝大多数排序类面试题了。因为快排可以延伸出 partition、减治、随机化、三路、荷兰国旗、TopK、最小 K 个数等一系列题目，性价比极高。归并排序要单独掌握，因为逆序对问题是它的主战场，这个下面会讲。

3. 牛客 TOP101 里那些绕不开的"二分+排序"综合题

3.1 旋转数组中的最小值：一个定义清晰但易错的问题

牛客二分排序专题里必有一道"旋转数组的最小数字"（比如 [3,4,5,1,2] 找最小值）。这道题看起来是找最小，实际上是二分查找的边界应用。关键思路是：每次取中间值，与右端点比较，判断最小值是在左半段还是右半段。

• 如果nums[mid] > nums[right]，说明最小值在 mid 右侧，因为这意味着左半段是完全递增的，而右侧有断崖（旋转点），最小值一定在右半段，可以left = mid + 1；
• 如果nums[mid] < nums[right]，说明右侧是递增的，最小值在左侧或者就是 mid，可以right = mid；
• 如果nums[mid] == nums[right]，无法判断，只能right--缩小范围。

第三种情况很多人容易漏。比如数组 [1, 1, 1, 0, 1]，mid 和 right 都是 1，你没法确定最小值在左还是右。此时安全的做法是把右边界向左移动一位，因为右端点值已经有了一个冗余，即使它是最小值，我们移动 one 也不会丢失最小值；如果它比最小值大，就更无所谓了。这个细节能展开说，面试官会认可你考虑问题比较全面。

3.2 合并区间与排序后的区间处理

"合并区间"是嵌套在排序里的经典题。思路是先按区间起点升序排列，然后遍历，用一个left和right维护当前合并区间的范围。如果下一个区间的起点大于当前right，说明无法合并，将当前区间加入结果并更新；否则需要将right更新为两者的较大值。

这里用到的排序不是简单的Arrays.sort排 int 数组，而是排对象：

Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

注意 Lambda 表达式可以直接写，但面试时面试官经常会问：为什么比较器返回负数、零、正数的含义？你要回答：比较器比较两个区间的起点，负数表示 a 排在 b 前面，零表示相等，正数表示 a 排在 b 后面。就这么一句话，很多人反而说不利索。

合并区间题的隐藏考点是边界处理。比如两个区间 [1,4] 和 [4,5] 算不算重叠？多数题目认为重叠，因为起点 4 和终点 4 相接，合并成 [1,5]；但也有的题目要求必须严格小于才算重叠。现场千万要和面试官确认这一点，或者直接说明你的假设。能主动定义边界条件，本身就是成熟的工程素养。

3.3 逆序对问题：归并排序的经典应用

逆序对问题是我认为二分/排序篇里最能拉开差距的题目。它要求在一个数组中找出所有满足"前一个数大于后一个数"的数对数量。暴力是 O(n²)，但用归并排序可以在合并过程中顺手统计，复杂度降到 O(n log n)。

原理是：归并排序的合并阶段，两个子数组分别已经有序。假设合并左半部分left[start..mid]和右半部分right[mid+1..end]，当左半边的某个元素nums[i]大于右半边的某个元素nums[j]时，nums[i]以及左半边 i 之后的所有元素都大于nums[j]，所以逆序对数可以直接累加mid - i + 1。

我在写这个题时出现过一次很迷惑的 bug：在合并完成后忘了把临时数组拷贝回原数组对应位置，结果统计结果正确但原数组被搞乱了，导致后续递归出错。所以这里一定要把"合并后覆盖回原数组"当作一个不可省略的步骤。面试时可以主动说："归并排序的关键在于合并时利用两段有序性，一次性跳过多个逆序对，这也是它比暴力快的原因。"

3.4 收尾：如何用二分思想降低排序后查询的复杂度

这个部分想聊聊综合题里常见的一个套路：先排序，再二分。比如给定一个数组，多次询问某个数是否存在，或者询问某个区间内有多少个数满足某个条件。如果没有预处理，每次查询都是 O(n)；但如果先排序，就可以用二分把单次查询降到 O(log n)。

这样的题在牛客上也很常见，比如"在排序数组中查找目标值的起止位置"，本质就是一次排序后对左右边界做两次二分。又比如"两数之和"如果用双指针，也得先排序。面试时如果遇到"无序数组 + 多次查找"的组合，脑子里应该立刻弹出"排序 + 二分"或者"排序 + 双指针"的思路。

我建议你做这一类综合题时，养成一个习惯：先把输入数据的范围、是否有序、是否有重复、是否需要稳定性写下来，再选算法。这不是浪费时间，而是避免面试官追问时你答不出选择理由。

4. 面试实战中的应变技巧：从看懂题目到写出满分答案

4.1 三分钟识别"可二分性"：什么题目能使用二分

很多人刷题时有这种感觉：看到题目答案用了二分，恍然大悟"哦原来这也行"，但自己在面试时就是想不到。原因是没有建立"可二分性"的识别模型。

使用二分的两个核心条件：

1. 区间具有单调性（从左到右满足条件的状态是连续的，比如目标值前面的元素都小于它，后面的都大于它）；
2. 可以在 O(1) 时间内判断某个中点是否符合条件。

很多"最大值最小化"问题（比如在数组中分割子数组使最大和最小）表面上是动态规划，但因为结果的可行性和 m 的大小单调，也能用二分答案去逼近。我见过不少面经出现这类题，如果你能在面试中提到"因为判定函数具有单调性，所以可以对答案做二分"，就会显得你思路很开阔。

判断是否可二分的快速方法是：把题目中的某个量当作自变量 x，如果"答案可行"这个性质随着 x 递增/递减是连续的，那么基本就可以二分。不要求你能严格证明，但要有这个意识。

4.2 如何口头讲述排序算法的复杂度与稳定性

面试官不一定让你现场写排序，而是会问"常用的排序有哪些？它们的复杂度和稳定性如何？"这种基础题，看似简单，却也最容易挂得冤枉。

我建议你准备一个表格记在脑子里：

面试时不仅要背，还要能说明为什么：比如快排最坏出现在每次 pivot 都是最小/最大值时，分治极不平衡；归并排序稳定是因为合并时优先取左半部分，相同元素的相对顺序不会被破坏；堆排序不稳定是因为堆调整的过程中会打乱相同元素的相对位置。

如果能举一个实际例子，比如排序对象是学生信息，先按学号排序，再按成绩稳定排序，就能在保持成绩排序的同时，让学号相同的分组内顺序不乱，那就更能加分。

4.3 现场调试二分死循环的经验谈

现场写二分最怕死循环，尤其面试官盯着屏幕的时候。我自己总结了几条快速自检策略：

• 检查 mid 的计算方式：如果区间长度为偶数，左中位是偏向 left 的。一旦更新分支里出现left = mid，请你立刻考虑是否要用右中位mid = left + (right - left + 1) / 2。这是最经典的死循环源头。
• 检查更新是否突破区间：如果你写right = mid，那么 right 的初始值应该表示"可能的位置"而不是"排除的位置"，否则可能漏掉 right 本身。
• 检查循环退出后是否需要后处理：采用"欢乐模板"（left+1<right）可以有效规避大部分死循环，但记住要检查两个最后候选。

还有一个土办法：随便取一个长度为 2 的小数组，比如[1, 3]，手动走一遍循环，如果 mid 不再变化或者 left/right 不再缩小，就能立刻发现问题。现场写代码时花十秒钟用笔在纸上演算一个最短用例，往往能帮你挽回一个严重的 bug。

4.4 最后说一句关于刷题节奏的个人体会

文章快结束时，分享一个我个人在牛客刷二分/排序篇时挺受用的小技巧。很多人喜欢按照题目顺序一路刷下去，但二分和排序题目的难度跳跃很大，前面的简单题会让你产生一种"我全会了"的错觉，直到后面遇到"数组中的逆序对"或者"二分答案"综合题，才瞬间被打击。

我建议你把整个二分/排序专题划分成三轮：

• 第一轮：只做精确查找、排序模板题，目的是把基础写法和边界情况刻进肌肉记忆。
• 第二轮：做旋转数组、TopK、合并区间这类变体题，每道题写完后，主动在代码旁边写一句注释，说明这个题用到了二分的哪个性质、排序的什么结构。
• 第三轮：做跨专题综合题，比如"先排序后二分"或者"二分答案"的题目，这轮的核心是练习题目抽象能力。

同时，面试前把 LeetCode 或牛客上这道题的官方题解和评论区高赞分析都翻一翻，看看不同写法之间的取舍。你会发现，同一道二分题，用闭区间、左闭右开、后处理三种写法都能过，但面试时你能解释清楚其中一种的优势，就已经比大多数人强了。

如果你现在正因为二分边界和排序变体题头疼，别慌。把你常用的模板固定下来，把上面这些边界情况和经典综合题的思路过一遍，再写几道找感觉，你会发现所谓的"二分排序篇（二）"其实内核非常集中：一个边界不迷路的二分，加一个能随手写出的 partition，再加一根"排序后能用二分优化查询"的弦，就足够陪你走过大部分面试场景了。