前阵子一个准备跳槽的朋友跟我聊天说他把牛客面试 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[mid1..end]当左半边的某个元素nums[i]大于右半边的某个元素nums[j]时nums[i]以及左半边 i 之后的所有元素都大于nums[j]所以逆序对数可以直接累加mid - i 1。我在写这个题时出现过一次很迷惑的 bug在合并完成后忘了把临时数组拷贝回原数组对应位置结果统计结果正确但原数组被搞乱了导致后续递归出错。所以这里一定要把合并后覆盖回原数组当作一个不可省略的步骤。面试时可以主动说归并排序的关键在于合并时利用两段有序性一次性跳过多个逆序对这也是它比暴力快的原因。3.4 收尾如何用二分思想降低排序后查询的复杂度这个部分想聊聊综合题里常见的一个套路先排序再二分。比如给定一个数组多次询问某个数是否存在或者询问某个区间内有多少个数满足某个条件。如果没有预处理每次查询都是 O(n)但如果先排序就可以用二分把单次查询降到 O(log n)。这样的题在牛客上也很常见比如在排序数组中查找目标值的起止位置本质就是一次排序后对左右边界做两次二分。又比如两数之和如果用双指针也得先排序。面试时如果遇到无序数组 多次查找的组合脑子里应该立刻弹出排序 二分或者排序 双指针的思路。我建议你做这一类综合题时养成一个习惯先把输入数据的范围、是否有序、是否有重复、是否需要稳定性写下来再选算法。这不是浪费时间而是避免面试官追问时你答不出选择理由。4. 面试实战中的应变技巧从看懂题目到写出满分答案4.1 三分钟识别可二分性什么题目能使用二分很多人刷题时有这种感觉看到题目答案用了二分恍然大悟哦原来这也行但自己在面试时就是想不到。原因是没有建立可二分性的识别模型。使用二分的两个核心条件区间具有单调性从左到右满足条件的状态是连续的比如目标值前面的元素都小于它后面的都大于它可以在 O(1) 时间内判断某个中点是否符合条件。很多最大值最小化问题比如在数组中分割子数组使最大和最小表面上是动态规划但因为结果的可行性和 m 的大小单调也能用二分答案去逼近。我见过不少面经出现这类题如果你能在面试中提到因为判定函数具有单调性所以可以对答案做二分就会显得你思路很开阔。判断是否可二分的快速方法是把题目中的某个量当作自变量 x如果答案可行这个性质随着 x 递增/递减是连续的那么基本就可以二分。不要求你能严格证明但要有这个意识。4.2 如何口头讲述排序算法的复杂度与稳定性面试官不一定让你现场写排序而是会问常用的排序有哪些它们的复杂度和稳定性如何这种基础题看似简单却也最容易挂得冤枉。我建议你准备一个表格记在脑子里排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定快速排序O(n log n)O(n²)O(log n)递归栈不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定面试时不仅要背还要能说明为什么比如快排最坏出现在每次 pivot 都是最小/最大值时分治极不平衡归并排序稳定是因为合并时优先取左半部分相同元素的相对顺序不会被破坏堆排序不稳定是因为堆调整的过程中会打乱相同元素的相对位置。如果能举一个实际例子比如排序对象是学生信息先按学号排序再按成绩稳定排序就能在保持成绩排序的同时让学号相同的分组内顺序不乱那就更能加分。4.3 现场调试二分死循环的经验谈现场写二分最怕死循环尤其面试官盯着屏幕的时候。我自己总结了几条快速自检策略检查 mid 的计算方式如果区间长度为偶数左中位是偏向 left 的。一旦更新分支里出现left mid请你立刻考虑是否要用右中位mid left (right - left 1) / 2。这是最经典的死循环源头。检查更新是否突破区间如果你写right mid那么 right 的初始值应该表示可能的位置而不是排除的位置否则可能漏掉 right 本身。检查循环退出后是否需要后处理采用欢乐模板left1right可以有效规避大部分死循环但记住要检查两个最后候选。还有一个土办法随便取一个长度为 2 的小数组比如[1, 3]手动走一遍循环如果 mid 不再变化或者 left/right 不再缩小就能立刻发现问题。现场写代码时花十秒钟用笔在纸上演算一个最短用例往往能帮你挽回一个严重的 bug。4.4 最后说一句关于刷题节奏的个人体会文章快结束时分享一个我个人在牛客刷二分/排序篇时挺受用的小技巧。很多人喜欢按照题目顺序一路刷下去但二分和排序题目的难度跳跃很大前面的简单题会让你产生一种我全会了的错觉直到后面遇到数组中的逆序对或者二分答案综合题才瞬间被打击。我建议你把整个二分/排序专题划分成三轮第一轮只做精确查找、排序模板题目的是把基础写法和边界情况刻进肌肉记忆。第二轮做旋转数组、TopK、合并区间这类变体题每道题写完后主动在代码旁边写一句注释说明这个题用到了二分的哪个性质、排序的什么结构。第三轮做跨专题综合题比如先排序后二分或者二分答案的题目这轮的核心是练习题目抽象能力。同时面试前把 LeetCode 或牛客上这道题的官方题解和评论区高赞分析都翻一翻看看不同写法之间的取舍。你会发现同一道二分题用闭区间、左闭右开、后处理三种写法都能过但面试时你能解释清楚其中一种的优势就已经比大多数人强了。如果你现在正因为二分边界和排序变体题头疼别慌。把你常用的模板固定下来把上面这些边界情况和经典综合题的思路过一遍再写几道找感觉你会发现所谓的二分排序篇二其实内核非常集中一个边界不迷路的二分加一个能随手写出的 partition再加一根排序后能用二分优化查询的弦就足够陪你走过大部分面试场景了。
