前一阵子有个做后端的朋友跟我聊起一个场景他的服务里有个配置表数据量不大不小大概几万条但每次请求都要判断某个ID在不在里面。最开始写法很直接for循环一遍后来流量涨了这个函数成了热点CUP占用一直下不来。我跟他说你要不要试试先把数组排个序然后用二分查找他很惊讶这都快2025年了谁还手写二分确实Java 里有Arrays.binarySearchPython 里有bisectC 里有std::binary_search看起来完全不需要自己写。但关键问题不在这两个函数本身而在于二分查找能用的前提是数据已经有序。而把无序数据变成有序这件事恰恰是快排最擅长的。把快排和二分查找放在一起不是一道教科书习题而是一套完整的高效查询方法论。这篇文章我想从工程和面试两个角度把这两个算法拆开揉碎了讲一遍。包括手写快排时那些容易踩的细节、二分查找的边界条件到底怎么记才不会乱、两者组合起来能解决什么实际问题以及在今天这个大部分语言都有内置排序和二分函数的前提下我们还需要理解它们的什么。全程以我实际写过的代码、排查过的性能问题为例希望能让你读完不只是懂了而是真正能在代码里用起来。1. 排序和二分查找从来不是两个孤立的算法很多人学数据结构的时候快排是排序章节的重头戏二分查找是查找章节的重头戏中间隔了好几节课再加上考试重点不同很少有人把这两个东西放在一起想。但实际工程里这两者的关系极其紧密甚至可以说二分查找的工程价值一半取决于前面那个排序排得有多好。1.1 从无序查找到有序查找的思维转变假设你手上有一个长度为 n 的数组现在要判断某个目标值在不在里面。如果你不做任何预处理那就只能线性扫描时间复杂度 O(n)。这个方案在 n 很小的时候没有任何问题十几二十个元素遍历一遍比什么都快。但一旦 n 变大比如到了十万、百万级别而且你要在短时间内反复查询成千上万次线性扫描的代价就会让人非常难受。这时候先排序、再二分的价值就体现出来了排序一次时间复杂度 O(n log n)摊销到后续每一次查询上之后每次查找只需要 O(log n)十万数据量的二分查找最多比较 17 次百万数据量也就 20 次。这个差距在数据量上了规模之后是极其恐怖的。假设你要查一万次一百万个元素线性扫描最坏情况要比较一万亿次而排序加二分只需要两千万次左右的比较相差五个数量级。1.2 快排本身就是为二分清扫障碍的角色二分查找只有一个硬性要求数据必须有序。而快排在众多排序算法里虽然最坏情况是 O(n²)但平均性能极佳且是原地排序、不需要额外大块内存。对于一个以排完序用来查为目标的任务来说快排几乎是最自然的选择。当然现代语言的内置排序早就不是单纯的教科书快排了C 的std::sort是内省排序Introspective SortGo 的sort.Slice在 1.19 之后也是基于 pdqsort 的改良版本。但无论底层怎么优化核心思想依然是找一个基准值把数据分成左右两半然后递归处理。理解了这个分治逻辑你才能真正理解排完序之后为什么二分能成立。1.3 两个算法共享的思想内核分治快排的核心动作是 partition分区选一个基准值把比它小的放左边、比它大的放右边。这一步做完之后左右两个区域分别递归处理。二分查找的核心动作也是在一个不断缩小的区间里做决策每次跟中点比较如果目标比中点小就去左半边找如果比中点大就去右半边找。每一轮把搜索区间缩小一半。两者的共同点在于每一轮处理完之后问题规模都在急剧缩小而缩小的方向是确定的。这个思想在很多更高级的算法里都会用到比如归并排序、快速选择、甚至某些树形结构。理解快排和二分之间的联系其实是在理解一套更底层的分而治之思维。2. 手写快排原理很简单细节很致命按理说快排的代码每个学编程的人都写过但很多人是背下来的不是理解下来的。一旦被问到为什么这个分区写法会死循环基准值该选哪个就支支吾吾说不清楚。这一节专门把快排实现里那些最容易出问题的地方掰开说清楚。2.1 几个必要的背景概念原地排序、稳定性、递归深度先说三个基本概念后面都会用到原地排序快排不需要申请额外的大数组来存放临时结果直接在当前数组上通过交换元素完成排序空间复杂度是 O(log n) 的递归栈开销。稳定性快排是不稳定的。所谓稳定指的是相等的元素在排序后保持原来的相对顺序。快排在交换过程中可能会把相等元素的前后顺序打乱所以它不是稳定排序。递归深度快排的性能极度依赖递归深度。如果基准值选得好递归树是平衡的深度大约 log n如果选得差每次都选到最大或最小值递归深度会退化成 n此时不仅时间复杂度变成 O(n²)还可能导致栈溢出。2.2 教科书版本的三种实现角度面试和考试中常见的快排写法大致可以分成三类最简单的新数组版本把小于基准和大于基准的元素分别放进两个新数组然后递归拼接。这个版本最好写但空间复杂度高、效率差一般只用来理解思路。挖坑法Hole Method以第一个元素作为基准值把它挖出来然后从右往左找比基准小的填到左边坑里再从左往右找比基准大的填到右边坑里最后把基准放回最后一个坑。双指针交换法Hoare/Lomuto 分区用两个索引从两端往中间走发现逆序对就交换。这也是大多数工程教材推荐的方式。实际手写时我推荐双指针交换法。代码清晰、分区效果好、不容易写出逻辑混乱的版本。下面给出一个我在实际项目中用过的双指针快排实现语言是 C 语言风格方便讲解核心逻辑void quick_sort(int arr[], int left, int right) { if (left right) return; int i left, j right; int pivot arr[left (right - left) / 2]; // 取中间值作为基准 while (i j) { while (arr[i] pivot) i; while (arr[j] pivot) j--; if (i j) { int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; i; j--; } } if (left j) quick_sort(arr, left, j); if (i right) quick_sort(arr, i, right); }注意这段代码里有几个关键细节pivot取的是中间位置的值而不是简单取arr[left]这可以在很大概率上避免最坏情况。内层两个while用的是严格小于和严格大于等于 pivot 的元素不参与交换而是留在原地等两侧向中间收敛。这样相等的元素不会在一个分区内反复来回移动也降低了无限循环的风险。外层while (i j)保证了循环结束时j i这样后续递归的边界[left, j]和[i, right]才不会重叠。2.3 手写快排最常见的三个坑坑一基准值选择不当导致最坏复杂度。如果数组已经是有序的而你每次选第一个元素作为基准分区结果是极端不平衡的一边是 n-1 个元素另一边是 0 个。这种情况下递归深度是 n时间复杂度是 O(n²)比冒泡排序好不到哪里去。解决思路很简单选中间位置、随机选一个位置或者三数取中取首、中、尾三个位置的中位数。坑二碰到大量重复元素时陷入死循环。假设数组是[2, 2, 2, 2, 2]基准是 2。如果内层循环用的是/指针会一直移动交换永远发生不了最终导致越界或死循环。解决办法就是上面代码里的严格小于/严格大于写法让等于基准的元素留在中间区域保证指针能正常交错。坑三递归边界写错导致栈溢出或漏排。递归结束时left right必须返回。实际代码中最容易犯的错是把if (left j)写成if (left i)或者边界不包含j、i本身。一定要记住跳出外层 while 之后j指向的是左半区最后一个位置i指向的是右半区第一个位置递归区间要包含这两个位置本身。2.4 工程环境下为什么要背刺教科书快排在面试里写一个教科书快排是为了展示基本功但在真实工程里我强烈建议不要自己手写排序直接使用语言内置的排序函数。原因有三个内置排序普遍采用混合策略如 Introsort数据量小的时候用插入排序递归深度过大时转堆排序规避快排最坏情况内置排序经过大量优化对 CPU 缓存、分支预测都有针对性调优手写版本很难跑赢内置排序通常支持传入自定义比较函数能灵活处理各种结构体、对象、倒序等需求。有一个清晰的边界如果你想理解快排的底层原理、应付面试、或者在某些不允许使用内置函数的竞赛环境中手写快排是必要的但在业务代码里内置排序永远是第一选择。这并不矛盾恰恰说明你真正理解了快排的适用场景。3. 二分查找的精髓不是折半是区间收敛很多人觉得二分查找太简单了无非就是取中间值比目标大就找左边比目标小就找右边。这么想没错但它没有触及二分查找最核心的东西——区间不变式。3.1 区间不变式每一次查找都发生在确定的范围内所谓区间不变式就是你在循环的每一轮开始时都能明确知道目标值如果存在一定位于当前这个区间内。 而二分查找的全部逻辑就是不断缩小这个区间同时保证不丢失目标。这个视角最大的好处是你不再需要死记left是小于mid还是小于等于mid这种问题了你只需要问自己一个问题——我下一步保留的区间是否仍然涵盖了所有可能的位置为了讲清楚这个我先把三种最常见的区间写法列出来对比。写法初始区间循环条件区间更新适用场景左闭右闭[0, n-1]left rightright mid - 1/left mid 1最常用找精确值左闭右开[0, n)left rightright mid/left mid 1找下界、条件判断型左开右开(-1, n)left 1 rightright mid/left mid手动控制已排除区域我自己最推荐的是左闭右闭也就是标准的[left, right]写法。它的优点在于非常直观初始化时left0, rightn-1循环里每次判断arr[mid]等于直接返回小于则改left mid 1大于则改right mid - 1。因为区间是闭的所以left和right都能取到循环条件必须是left right才能保证最后一次单元素区间也被检查到。3.2 一个很经典的问题mid 计算为什么要防溢出有个老生常谈但依然值得强调的细节mid (left right) / 2在left和right都非常大的时候可能溢出。比如left 10^9right 10^9两者相加是2 * 10^9在 32 位整数环境下已经逼近甚至超过上限。更安全的写法是int mid left (right - left) / 2;这个写法先求出区间长度的一半再加上左边界永远不会溢出。这不是教科书为了严谨才说的而是我在实际处理超大数据量时真实踩过的坑。3.3 从找一个值到找边界lower_bound 和 upper_bound实际业务里二分查找最常见的需求其实不是找一个精确值在不在而是以下三种找第一个大于等于目标值的位置lower_bound。找第一个大于目标值的位置upper_bound。找最后一个等于目标值的位置。这三个需求本质上都是区间收敛的变体只是条件判断和返回时机不同。以 C 的lower_bound为例它的逻辑是int lower_bound(vectorint nums, int target) { int left 0, right nums.size(); // 左闭右开 while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid; // 目标在左半区且 mid 可能是答案所以不减 1 } else { left mid 1; } } return left; }这里的关键是当nums[mid] target时mid本身可能就是第一个大于等于 target 的位置因此right不能等于mid - 1而应该等于mid把这个可能性保留下来。这也是区间收敛视角的价值所在——你不需要背代码只需要不断问自己这个位置有没有可能是最终答案。3.4 死循环、越界、漏查二分查找的排错实战二分查找的 bug 非常隐蔽往往不是直接崩溃而是返回一个差一个位置的结果。我在 Code Review 里见过的最常见的错误有两个错误一更新区间时把mid漏掉了。比如在找下界时nums[mid] target却写成了right mid - 1结果正确答案刚好是mid直接漏掉。错误二循环终止条件写错。比如用了左闭右闭区间却写while (left right)那最后一个元素永远不会被检查结果就是数组里明明有这个数函数告诉你没有。排错方法很简单写两个测试用例一个目标值在数组首位一个在数组末位。再加一个目标值不存在的用例。这三个用例几乎能覆盖绝大多数逻辑错误。如果你用的语言自带了二分查找函数直接从内置函数的结果作为基准做随机测试对比是最快的方式。4. 快排加二分查找的经典组合场景、代码与性能分析讲完两个算法的原理现在把它们真正组合起来用。这一节会围绕一个我实际做过的小工具展开给定一个无序的用户 ID 列表快速实现多个这个 ID 是否存在的查询。4.1 最直接的业务场景离线批量查询工作里经常遇到这种需求有一份目标数据比如黑名单、白名单、已领取优惠券的用户集合数据量是几万到几十万然后你需要在一个请求里判断大量 ID 是否命中。最简单粗暴的解法是用哈希集合HashSet。但如果这个名单需要频繁从远端拉取、内存特别受限、或者你要在一个非常朴素的嵌入式环境里跑哈希的额外开销可能并不理想。这时候排序二分就是一个很优雅的替代方案把名单排序一次后续每个查询用二分查找判断是否存在整个数据结构就是一个有序数组没有额外指针或哈希桶内存占用比哈希集合低得多。const list [/* 大量无序ID */]; list.sort((a, b) a - b); // 排序一次等效于快排思路 function exists(id) { let left 0, right list.length - 1; while (left right) { const mid (left right) 1; if (list[mid] id) return true; if (list[mid] id) left mid 1; else right mid - 1; } return false; }这段代码在浏览器端和 Node.js 里都可以直接跑。Array.prototype.sort在 V8 引擎里使用的是一种改良过的快速排序旧版和 TimSort新版整体性能都很可靠。4.2 面试/竞赛中的组合题两数之和、区间统计、第 K 大问题面试和算法竞赛里排序二分是一个极其常见的解题套路。很多题目看不出直接关系但一旦你先排序问题就豁然开朗。典型例子两数之和变体。原题是找两个数使得它们的和等于 target常见解法是哈希表但哈希表会占用额外空间。如果你要求空间复杂度 O(1)思路就变成先排序然后固定一个数用二分查找找target - 当前数。这样时间 O(n log n)空间 O(1)在某些约束下反而是更优解。典型例子统计区间内元素个数。给你一个无序数组以及若干组查询[L, R]需要统计数组中值在 L 和 R 之间的元素个数。先排序然后对每一组查询分别用 lower_bound 找 L 的位置、upper_bound 找 R 的位置位置相减就是个数。每个查询 O(log n)比每次遍历整个数组快得多。典型例子快速选择/第 K 大问题。先排序直接通过下标拿到第 K 大是一种朴素但绝对正确、且非常好写的解法。虽然最优解是快速选择 O(n)但在数据量不大、追求代码可读性和正确性的场景下排序BFS 的解法依然有其价值。4.3 性能对比快排二分 vs. 哈希表 vs. 线性扫描这里用一组粗略的估算数据来说明问题。假设 n 100000查询次数 m 100000。方案预处理耗时单次查询耗时总耗时量级额外空间线性扫描无O(n)O(n·m) ≈ 10^10O(1)排序后二分O(n log n)O(log n)O(n log n m log n) ≈ 3×10^6O(log n) 递归栈哈希表O(n)O(1) 平均O(n m) ≈ 2×10^5O(n)从这个表能看出来一个很务实的结论如果 m 很大哈希表通常更快如果内存受限、或者不想依赖哈希函数质量排序二分是非常稳妥的选择。如果 m 很小比如只查一两次那线性扫描可能反而是最快的因为省去了排序的开销。所以在实际项目中我的选择原则是查询次数多、内存充裕用哈希集合查询次数多、内存受限或数据需要保证有序性排序二分查询次数少、数据量不大直接遍历别过度设计。4.4 使用场景的边界什么时候不该用快排二分这个组合不是银弹有几个场景我明确不推荐。频繁插入/删除的动态数据集。数组排序后如果频繁增删元素每次插入都要维持有序性代价是 O(n) 的移动比二分查找减少的那些开销可能全赔回去。这时候应该考虑平衡二叉树、跳表或者直接用哈希结构。数据量极小。只有几十个元素时二分的常数开销比较、索引跳转未必比线性扫描快多少。JVM 或 V8 的 JIT 编译器对简单的线性循环优化非常好有时候反而更快。需要范围查询且数据实时变化。这种情况更合适的方案是线段树、树状数组而不是排序数组。5. 工程落地的细节与实战心得语言内置函数、边界条件、常见坑讲完原理和场景最后聊聊把这些东西真正落到工程里时积累的一些经验和教训。这部分是最琐碎、最容易在文档里看不到的。5.1 各大语言内置函数的正确用法现在的工程代码我原则上是能不手写就不手写。每个语言都有成熟的排序和二分函数关键在于用对。Pythonbisect模块是神器。bisect_left和bisect_right分别对应 lower_bound 和 upper_bound。一个非常常见的用法是在一个有序列表里统计某个值的出现次数import bisect nums [1, 3, 3, 3, 5] left bisect.bisect_left(nums, 3) right bisect.bisect_right(nums, 3) print(right - left) # 输出 3Cstd::sortstd::binary_search/std::lower_bound。std::binary_search只告诉你在不在lower_bound给你迭代器位置后者信息量更大。JavaArrays.sortArrays.binarySearch。注意Arrays.binarySearch在找不到目标时返回的是-(插入点) - 1这个负数结果可以直接用来算应该插入的位置。Gosort.Search是一个通用二分框架。它接受一个函数返回第一个让函数返回true的下标非常灵活。5.2 排序索引丢失问题排序前先想想你还需要什么排序有一个很隐蔽的坑你排完序原始数据的相对位置就丢了。有时候你不仅想知道某个值在不在还想知道它在原数组里的下标是什么、它对应的对象是什么。解决办法是在排序前先给每个元素记一个原始下标然后用结构体/元组排序type Item struct { Value int Index int } items : make([]Item, len(original)) for i, v : range original { items[i] Item{Value: v, Index: i} } sort.Slice(items, func(i, j int) bool { return items[i].Value items[j].Value })这样排完之后元素在原数组中的位置依然可以通过Index字段拿到。这个技巧在处理排序后还要还原或者对应其他数组的场景时特别管用。5.3 重复元素场景下的二分策略如果数组里有大量重复值二分查找返回某个位置并不意味着第一个或者最后一个。这时候要用lower_bound和upper_bound的组合才能拿到完整的重复区间。举一个实际业务里的例子我们有一个日志表按时间戳排序存储需要查询某个时间窗口内有哪些记录。这个窗口的左右边界就分别对应lower_bound(startTime)和upper_bound(endTime)两者之间的所有记录就是答案。这个思路比找到任意一个匹配时间戳再左右扩展要简洁可靠得多。5.4 浮点数比较带来的二分陷阱工程里二分查找的对象不一定是整数还有可能是浮点数。浮点数二分有个额外的坑你不能用来判断精确相等因为浮点数有精度误差。正确做法是要么设定一个精度阈值eps要么通过固定迭代次数来收敛。比如double left -1e9, right 1e9; for (int i 0; i 100; i) { // 直接迭代固定次数 double mid (left right) / 2; if (check(mid)) right mid; else left mid; }迭代 100 次已经能把[0, 1e9]的区间收敛到极小范围完全够用。这种固定次数迭代的写法比判断区间长度小于 eps更稳因为避免了因 eps 设置不当导致的死循环。5.5 自定义比较函数的排序一致性还有一个我在 Code Review 里反复强调的点排序用的比较函数和二分用的比较函数必须完全一致。如果排序时按升序排二分时却写反了大小判断结果必然全部错乱。更隐蔽的是如果比较函数里带了多个字段比如先按分数排、再按时间排那二分查找时这多个字段全部要参与判断不能只比较其中一个。解决这个问题的最好方式是把比较逻辑抽成一个具名函数排序和二分都调用同一个函数从机制上杜绝两端不一致的可能。最后聊点实在的回头看一下这篇文章的核心其实就一句话二分查找的前提是数据有序而快排是为你铺好这条路的最高效方式之一。但真正值钱的不是这两个算法本身而是你怎么在合适的场景里组合它们、怎么写对边界条件、怎么避开那些看起来不起眼却能让你排查一晚上的隐藏坑。我个人在实际项目里的体会是现代语言内置的排序和二分函数已经足够强大绝大多数情况下直接调库就好。但你依然需要理解底层原理因为只有理解了原理你才知道内置函数为什么那样设计、什么时候该用哪种变体、出了问题该从哪里排查。最后分享一个实操小技巧如果你要在一个有序数组里反复查找别急着写二分。先看看语言有没有内置的 bisect / binarySearch有就直接用如果没有再自己写。写完别忘了我前面说的三个测试用例——目标在首位、目标在末位、目标不存在。就这三个用例足以拦住 90% 的二分 bug。