tech-interview-handbook 排序与搜索专题复杂度对比、二分查找源码剖析与刷题路线【免费下载链接】tech-interview-handbookCurated coding interview preparation materials for busy software engineers项目地址: https://gitcode.com/GitHub_Trending/te/tech-interview-handbook本文基于 tech-interview-handbook 仓库中的排序与搜索专题速查文档sorting-searching.md完整覆盖其核心脉络各排序算法的时间/空间复杂度对比、语言内置排序算法真相、二分查找及其变体的可运行源码实现、面试中必须识别的两类技巧有序输入、有限值域以及必备题与推荐刷题清单。读完后你应能判断一道题该用二分还是直接调用语言默认排序默写出无溢出风险的迭代版二分查找与 bisect 变体并用仓库中自带的可运行参考实现自测。排序与搜索为什么是同一个专题排序Sorting是将序列中的元素按数值或字典序重新排列的操作可以是升序也可以是降序。速查文档的开篇就给出了一个关键的面试认知一批基础排序算法的时间复杂度是 O(n²)不应该在面试中使用。在算法面试中你几乎不需要从零实现任何排序算法。正确做法是用语言内置的排序函数对输入排序使其可以被二分搜索。也就是说面试中排序的定位是预处理手段——先把输入排好再叠加 O(log n) 的二分搜索。对于已排序数组二分搜索利用其有序性质将目标值与数组中间元素比较从而确定目标位于左半还是右半然后在剩下的半区中继续比较直到找到目标或区间为空。各排序算法复杂度总览原文档给出了完整的复杂度对照表这是面试中被问说说常见排序的复杂度时的标准答案务必完整掌握算法时间复杂度空间复杂度冒泡排序 Bubble sortO(n²)O(1)插入排序 Insertion sortO(n²)O(1)选择排序 Selection sortO(n²)O(1)快速排序 QuicksortO(n log n)O(log n)归并排序 MergesortO(n log n)O(n)堆排序 HeapsortO(n log n)O(1)计数排序 Counting sortO(n k)O(k)基数排序 Radix sortO(nk)O(n k)算法Big-O二分搜索 Binary searchO(log n))两个细节值得注意Mergesort 的 O(n) 空间来自合并时需要额外数组可参考后文 mergeSort.js 的实现Heapsort 之所以能原地排序是因为堆可以就地构建在数组上参考 heap.py。Counting sort 与 Radix sort 的复杂度依赖 k值域大小/位数它们是唯一的非比较排序这也是后文有限值域技巧的理论基础。面试必知你语言的默认排序算法到底是什么原文档特别提醒必须知道你所用语言默认排序算法的时间和空间复杂度。其时间复杂度几乎肯定是 O(n log n)如果能说出具体算法名则是加分项。文档给出的事实如下Python 3.11默认排序算法是 Powersort它取代了此前一直使用的 TimsortJava对象排序使用 Timsort 的实现基本类型primitives排序使用 Dual-Pivot Quicksort双轴快排。这条信息在面试口头表达中很实用——比如被问Python 的 sorted() 稳定吗时可以顺着 Timsort/Powersort 的稳定性与 O(n log n) 复杂度展开。边界情况Corner Cases原文档列出的边界情况清单同样是二分与排序实现的自测清单任何手写二分/排序代码都应逐条过一遍空序列Empty sequence只有一个元素的序列有两个元素的序列含重复元素的序列仓库中自带的参考实现正是按这套清单写的测试用例例如 mergeSort.js 就依次验证了空数组、单元素、双元素、含重复元素[7, 2, 4, 3, 1, 2]期望[1, 2, 2, 3, 4, 7]、已有序数组与含负数的数组可作为自测模板直接沿用。二分搜索的无溢出迭代实现速查文档的核心结论——有序输入首先想到二分——在仓库中有可直接运行的参考实现。JavaScript 版本见 binarySearch.jsfunction binarySearch(arr, target) { let left 0; let right arr.length - 1; while (left right) { const mid left Math.floor((right - left) / 2); if (arr[mid] target) { return mid; } if (arr[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }Python 等价实现见 binary_search.pydef binary_search(arr, target): left 0 right len(arr) - 1 while left right: mid left (right - left) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 else: right mid - 1 return -1两处实现都体现了两个关键工程细节面试手撕时应当刻意保留中点计算用left (right - left) // 2而非(left right) // 2。在 C/Java 等语言中left right可能溢出这种写法避免了该问题循环条件left right且返回 -1 表示未命中而不是返回布尔值——返回下标能让调用方拿到目标位置。两个文件末尾都附带了断言式自测对[1, 2, 3, 10]分别查找首元素、中间元素、尾元素、不存在元素、小于首元素与大于尾元素的值全部符合预期覆盖了命中/不命中/越界两侧的组合。bisect 变体处理重复元素与插入位置binary_search.py 还实现了二分搜索最重要的两个变体bisect_left和bisect_right它们回答的问题不是目标在哪而是目标应该插到哪里才能保持有序def bisect_left(arr, target): Returns the leftmost position that target should go to such that the sequence remains sorted. left 0 right len(arr) while left right: mid (left right) // 2 if arr[mid] target: left mid 1 else: right mid return left def bisect_right(arr, target): Returns the rightmost position that target should go to such that the sequence remains sorted. left 0 right len(arr) while left right: mid (left right) // 2 if arr[mid] target: right mid else: left mid 1 return left注意与基础二分的三点结构差异搜索区间右端是len(arr)而非len(arr) - 1允许插入到末尾循环条件是left right左闭右开区间比较方向不同bisect_left用bisect_right用。文件内的自测用例第 50-68 行特别验证了重复元素场景对[1, 2, 3, 3, 10]查找 3bisect_left返回 2第一个 3 的位置bisect_right返回 4最后一个 3 之后的位置——这正是原文档含重复元素的序列这一边界情况的具体化。这类变体是 Search in Rotated Sorted Array、统计区间内元素个数等高频题的骨架。归并排序实现为什么它的空间是 O(n)仓库中 mergeSort.js 提供了一个标准的递归归并排序实现恰好印证了复杂度表中的空间一栏function mergeSort(arr) { if (arr.length 2) { // Arrays of length 0 or 1 are sorted by definition. return arr; } const left arr.slice(0, Math.floor(arr.length / 2)); const right arr.slice(Math.floor(arr.length / 2), arr.length); return merge(mergeSort(left), mergeSort(right)); } function merge(arr1, arr2) { const merged []; let i 0, j 0; while (i arr1.length j arr2.length) { if (arr1[i] arr2[j]) { merged.push(arr1[i]); i; } else if (arr2[j] arr1[i]) { merged.push(arr2[j]); j; } } merged.push(...arr1.slice(i), ...arr2.slice(j)); return merged; }从源码结构看每个slice与merged数组都会分配新内存递归深度为 log n、每层合计复制 n 个元素因此总空间开销是 O(n)——这就是它与原地排序O(1) 空间的 Heapsort的核心取舍也是 Mergesort 稳定比较保证相等元素保持原相对顺序而 Heapsort 不稳定见 heap.py 中_bubble_down选较小子节点时左子优先的写法的原因。虽然面试不要求你默写归并排序但理解为什么需要额外 O(n) 空间能在复杂度讨论中体现深度。文件末尾第 34-50 行的自测用例覆盖了原文档列出的全部边界情况空数组、单元素、双元素、重复元素、逆序数组以及含负数数组。从排序到选择QuickSelect 与 K 大问题原文档推荐练习题中包含 Kth Largest Element in an Array 这类 K 大问题。这类问题的最优解法不是完整排序而是 QuickSelect——基于快排 partition 思想的线性时间选择算法。仓库中的 quick_select.py 给出了可运行实现def quick_select(array, k): NOTE: k-th smallest element counts from 0! left 0 right len(array) while True: random_index random.sample(range(left, right), 1)[0] array[left], array[random_index] array[random_index], array[left] pivot_index partition_first(array, left, right) if k pivot_index: return array[pivot_index] if k pivot_index: right pivot_index else: left pivot_index 1实现要点从源码中可以读出随机化选轴元避免最坏 O(n²)partition_first变体保证轴元落在其最终排序位置这是正确性前提每轮只递归/循环进入一侧因此期望复杂度 O(n)。文件末尾第 50-60 行用 1000 个元素随机打乱 10 次的随机化测试来验证这种大规模随机自测的写法在面试白板之外非常实用。面试中的两类识别技巧原文档的 Techniques 一节给出了两条题目识别规则这是把排序/搜索专题落地到具体题目的桥梁1. 输入已经有序Sorted inputs当给定序列本身有序无论升序还是降序时二分搜索应该是你脑海中第一个跳出来的工具。这一条覆盖的题型包括有序数组/旋转有序数组中的搜索、二维有序矩阵的搜索、用二分搜索答案的单调性问题如求最小的 x 使 f(x) 成立。前面讲的 bisect 变体正是这条技巧的具体工具。2. 值域有限的输入Limited range计数排序Counting sort是一种非比较排序适用于事先已知取值范围的数值。原文档给出的例子是 H-Index 问题。当 n 很大但值域 k 很小或 k 与 n 同量级时O(n k) 的计数排序可以击败 O(n log n) 的比较排序这也解释了复杂度表中为什么单独列出 Counting sort 与 Radix sort。刷题清单必备题与推荐题原文档将练习分为必备题学习本专题时优先刷与推荐题学完必备题后刷以下为完整继承的清单必备题Essential questionsBinary SearchLeetCode 704——二分基础模板题Search in Rotated Sorted ArrayLeetCode 33——有序性被破坏后的二分推荐练习题Recommended practice questionsKth Smallest Element in a Sorted MatrixLeetCode 378——有序结构上的二分Search a 2D MatrixLeetCode 74——把二维矩阵摊平成一维二分Kth Largest Element in an ArrayLeetCode 215——QuickSelect 的直接应用Find Minimum in Rotated Sorted ArrayLeetCode 153——旋转数组中用二分找拐点Median of Two Sorted ArraysLeetCode 4——两个有序数组上的二分难度上限这份清单与仓库内参考实现的对应关系很直接旋转数组两题练有序性判定Kth 两题练二分/选择代替全排序矩阵两题练降维后二分Median 一题练对答案空间二分。学习资源按原文档继承原文档按阅读/加餐/视频三层组织了学习资源。外部链接因平台规范不再列出但保留其来源与主题供检索核心阅读basecs 的排序算法基础文、Khan Academy 的 Binary Search 讲解加餐有时间再看basecs 系列文章覆盖 Selection Sort、Bubble Sort、Insertion Sort、Merge Sort上下篇、Quicksort上下篇、Counting Sort、Radix Sort视频系列剑桥大学 Samuel Albanie 的算法短视频覆盖 Heapsort、Quicksort、比较排序下界Lower bounds for comparison sorts、Counting sort、Radix sort、Bucket sort每支视频均配有 slides。仓库本身也提供了算法课程的推荐入口见 AlgorithmCourses.md按专题文档的引用方式挂载在本页末尾。小结排序与搜索专题在面试中的真实分工是排序靠语言内置函数Python 3.11 的 Powersort、Java 的 Timsort/双轴快排搜索才是手撕重点。建议的掌握路径是先背下复杂度对照表 → 用 binarySearch.js 与 binary_search.py 把基础二分和 bisect 变体各手撕两遍并跑通自带自测用例 → 理解 mergeSort.js 的 O(n) 空间来源 → 通过 quick_select.py 建立选择代替排序的直觉 → 按必备题、推荐题顺序完成刷题并对每个实现逐条核对原文档的四类边界情况空、单元素、双元素、重复元素。【免费下载链接】tech-interview-handbookCurated coding interview preparation materials for busy software engineers项目地址: https://gitcode.com/GitHub_Trending/te/tech-interview-handbook创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
tech-interview-handbook 排序与搜索专题：复杂度对比、二分查找源码剖析与刷题路线
tech-interview-handbook 排序与搜索专题复杂度对比、二分查找源码剖析与刷题路线【免费下载链接】tech-interview-handbookCurated coding interview preparation materials for busy software engineers项目地址: https://gitcode.com/GitHub_Trending/te/tech-interview-handbook本文基于 tech-interview-handbook 仓库中的排序与搜索专题速查文档sorting-searching.md完整覆盖其核心脉络各排序算法的时间/空间复杂度对比、语言内置排序算法真相、二分查找及其变体的可运行源码实现、面试中必须识别的两类技巧有序输入、有限值域以及必备题与推荐刷题清单。读完后你应能判断一道题该用二分还是直接调用语言默认排序默写出无溢出风险的迭代版二分查找与 bisect 变体并用仓库中自带的可运行参考实现自测。排序与搜索为什么是同一个专题排序Sorting是将序列中的元素按数值或字典序重新排列的操作可以是升序也可以是降序。速查文档的开篇就给出了一个关键的面试认知一批基础排序算法的时间复杂度是 O(n²)不应该在面试中使用。在算法面试中你几乎不需要从零实现任何排序算法。正确做法是用语言内置的排序函数对输入排序使其可以被二分搜索。也就是说面试中排序的定位是预处理手段——先把输入排好再叠加 O(log n) 的二分搜索。对于已排序数组二分搜索利用其有序性质将目标值与数组中间元素比较从而确定目标位于左半还是右半然后在剩下的半区中继续比较直到找到目标或区间为空。各排序算法复杂度总览原文档给出了完整的复杂度对照表这是面试中被问说说常见排序的复杂度时的标准答案务必完整掌握算法时间复杂度空间复杂度冒泡排序 Bubble sortO(n²)O(1)插入排序 Insertion sortO(n²)O(1)选择排序 Selection sortO(n²)O(1)快速排序 QuicksortO(n log n)O(log n)归并排序 MergesortO(n log n)O(n)堆排序 HeapsortO(n log n)O(1)计数排序 Counting sortO(n k)O(k)基数排序 Radix sortO(nk)O(n k)算法Big-O二分搜索 Binary searchO(log n))两个细节值得注意Mergesort 的 O(n) 空间来自合并时需要额外数组可参考后文 mergeSort.js 的实现Heapsort 之所以能原地排序是因为堆可以就地构建在数组上参考 heap.py。Counting sort 与 Radix sort 的复杂度依赖 k值域大小/位数它们是唯一的非比较排序这也是后文有限值域技巧的理论基础。面试必知你语言的默认排序算法到底是什么原文档特别提醒必须知道你所用语言默认排序算法的时间和空间复杂度。其时间复杂度几乎肯定是 O(n log n)如果能说出具体算法名则是加分项。文档给出的事实如下Python 3.11默认排序算法是 Powersort它取代了此前一直使用的 TimsortJava对象排序使用 Timsort 的实现基本类型primitives排序使用 Dual-Pivot Quicksort双轴快排。这条信息在面试口头表达中很实用——比如被问Python 的 sorted() 稳定吗时可以顺着 Timsort/Powersort 的稳定性与 O(n log n) 复杂度展开。边界情况Corner Cases原文档列出的边界情况清单同样是二分与排序实现的自测清单任何手写二分/排序代码都应逐条过一遍空序列Empty sequence只有一个元素的序列有两个元素的序列含重复元素的序列仓库中自带的参考实现正是按这套清单写的测试用例例如 mergeSort.js 就依次验证了空数组、单元素、双元素、含重复元素[7, 2, 4, 3, 1, 2]期望[1, 2, 2, 3, 4, 7]、已有序数组与含负数的数组可作为自测模板直接沿用。二分搜索的无溢出迭代实现速查文档的核心结论——有序输入首先想到二分——在仓库中有可直接运行的参考实现。JavaScript 版本见 binarySearch.jsfunction binarySearch(arr, target) { let left 0; let right arr.length - 1; while (left right) { const mid left Math.floor((right - left) / 2); if (arr[mid] target) { return mid; } if (arr[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }Python 等价实现见 binary_search.pydef binary_search(arr, target): left 0 right len(arr) - 1 while left right: mid left (right - left) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 else: right mid - 1 return -1两处实现都体现了两个关键工程细节面试手撕时应当刻意保留中点计算用left (right - left) // 2而非(left right) // 2。在 C/Java 等语言中left right可能溢出这种写法避免了该问题循环条件left right且返回 -1 表示未命中而不是返回布尔值——返回下标能让调用方拿到目标位置。两个文件末尾都附带了断言式自测对[1, 2, 3, 10]分别查找首元素、中间元素、尾元素、不存在元素、小于首元素与大于尾元素的值全部符合预期覆盖了命中/不命中/越界两侧的组合。bisect 变体处理重复元素与插入位置binary_search.py 还实现了二分搜索最重要的两个变体bisect_left和bisect_right它们回答的问题不是目标在哪而是目标应该插到哪里才能保持有序def bisect_left(arr, target): Returns the leftmost position that target should go to such that the sequence remains sorted. left 0 right len(arr) while left right: mid (left right) // 2 if arr[mid] target: left mid 1 else: right mid return left def bisect_right(arr, target): Returns the rightmost position that target should go to such that the sequence remains sorted. left 0 right len(arr) while left right: mid (left right) // 2 if arr[mid] target: right mid else: left mid 1 return left注意与基础二分的三点结构差异搜索区间右端是len(arr)而非len(arr) - 1允许插入到末尾循环条件是left right左闭右开区间比较方向不同bisect_left用bisect_right用。文件内的自测用例第 50-68 行特别验证了重复元素场景对[1, 2, 3, 3, 10]查找 3bisect_left返回 2第一个 3 的位置bisect_right返回 4最后一个 3 之后的位置——这正是原文档含重复元素的序列这一边界情况的具体化。这类变体是 Search in Rotated Sorted Array、统计区间内元素个数等高频题的骨架。归并排序实现为什么它的空间是 O(n)仓库中 mergeSort.js 提供了一个标准的递归归并排序实现恰好印证了复杂度表中的空间一栏function mergeSort(arr) { if (arr.length 2) { // Arrays of length 0 or 1 are sorted by definition. return arr; } const left arr.slice(0, Math.floor(arr.length / 2)); const right arr.slice(Math.floor(arr.length / 2), arr.length); return merge(mergeSort(left), mergeSort(right)); } function merge(arr1, arr2) { const merged []; let i 0, j 0; while (i arr1.length j arr2.length) { if (arr1[i] arr2[j]) { merged.push(arr1[i]); i; } else if (arr2[j] arr1[i]) { merged.push(arr2[j]); j; } } merged.push(...arr1.slice(i), ...arr2.slice(j)); return merged; }从源码结构看每个slice与merged数组都会分配新内存递归深度为 log n、每层合计复制 n 个元素因此总空间开销是 O(n)——这就是它与原地排序O(1) 空间的 Heapsort的核心取舍也是 Mergesort 稳定比较保证相等元素保持原相对顺序而 Heapsort 不稳定见 heap.py 中_bubble_down选较小子节点时左子优先的写法的原因。虽然面试不要求你默写归并排序但理解为什么需要额外 O(n) 空间能在复杂度讨论中体现深度。文件末尾第 34-50 行的自测用例覆盖了原文档列出的全部边界情况空数组、单元素、双元素、重复元素、逆序数组以及含负数数组。从排序到选择QuickSelect 与 K 大问题原文档推荐练习题中包含 Kth Largest Element in an Array 这类 K 大问题。这类问题的最优解法不是完整排序而是 QuickSelect——基于快排 partition 思想的线性时间选择算法。仓库中的 quick_select.py 给出了可运行实现def quick_select(array, k): NOTE: k-th smallest element counts from 0! left 0 right len(array) while True: random_index random.sample(range(left, right), 1)[0] array[left], array[random_index] array[random_index], array[left] pivot_index partition_first(array, left, right) if k pivot_index: return array[pivot_index] if k pivot_index: right pivot_index else: left pivot_index 1实现要点从源码中可以读出随机化选轴元避免最坏 O(n²)partition_first变体保证轴元落在其最终排序位置这是正确性前提每轮只递归/循环进入一侧因此期望复杂度 O(n)。文件末尾第 50-60 行用 1000 个元素随机打乱 10 次的随机化测试来验证这种大规模随机自测的写法在面试白板之外非常实用。面试中的两类识别技巧原文档的 Techniques 一节给出了两条题目识别规则这是把排序/搜索专题落地到具体题目的桥梁1. 输入已经有序Sorted inputs当给定序列本身有序无论升序还是降序时二分搜索应该是你脑海中第一个跳出来的工具。这一条覆盖的题型包括有序数组/旋转有序数组中的搜索、二维有序矩阵的搜索、用二分搜索答案的单调性问题如求最小的 x 使 f(x) 成立。前面讲的 bisect 变体正是这条技巧的具体工具。2. 值域有限的输入Limited range计数排序Counting sort是一种非比较排序适用于事先已知取值范围的数值。原文档给出的例子是 H-Index 问题。当 n 很大但值域 k 很小或 k 与 n 同量级时O(n k) 的计数排序可以击败 O(n log n) 的比较排序这也解释了复杂度表中为什么单独列出 Counting sort 与 Radix sort。刷题清单必备题与推荐题原文档将练习分为必备题学习本专题时优先刷与推荐题学完必备题后刷以下为完整继承的清单必备题Essential questionsBinary SearchLeetCode 704——二分基础模板题Search in Rotated Sorted ArrayLeetCode 33——有序性被破坏后的二分推荐练习题Recommended practice questionsKth Smallest Element in a Sorted MatrixLeetCode 378——有序结构上的二分Search a 2D MatrixLeetCode 74——把二维矩阵摊平成一维二分Kth Largest Element in an ArrayLeetCode 215——QuickSelect 的直接应用Find Minimum in Rotated Sorted ArrayLeetCode 153——旋转数组中用二分找拐点Median of Two Sorted ArraysLeetCode 4——两个有序数组上的二分难度上限这份清单与仓库内参考实现的对应关系很直接旋转数组两题练有序性判定Kth 两题练二分/选择代替全排序矩阵两题练降维后二分Median 一题练对答案空间二分。学习资源按原文档继承原文档按阅读/加餐/视频三层组织了学习资源。外部链接因平台规范不再列出但保留其来源与主题供检索核心阅读basecs 的排序算法基础文、Khan Academy 的 Binary Search 讲解加餐有时间再看basecs 系列文章覆盖 Selection Sort、Bubble Sort、Insertion Sort、Merge Sort上下篇、Quicksort上下篇、Counting Sort、Radix Sort视频系列剑桥大学 Samuel Albanie 的算法短视频覆盖 Heapsort、Quicksort、比较排序下界Lower bounds for comparison sorts、Counting sort、Radix sort、Bucket sort每支视频均配有 slides。仓库本身也提供了算法课程的推荐入口见 AlgorithmCourses.md按专题文档的引用方式挂载在本页末尾。小结排序与搜索专题在面试中的真实分工是排序靠语言内置函数Python 3.11 的 Powersort、Java 的 Timsort/双轴快排搜索才是手撕重点。建议的掌握路径是先背下复杂度对照表 → 用 binarySearch.js 与 binary_search.py 把基础二分和 bisect 变体各手撕两遍并跑通自带自测用例 → 理解 mergeSort.js 的 O(n) 空间来源 → 通过 quick_select.py 建立选择代替排序的直觉 → 按必备题、推荐题顺序完成刷题并对每个实现逐条核对原文档的四类边界情况空、单元素、双元素、重复元素。【免费下载链接】tech-interview-handbookCurated coding interview preparation materials for busy software engineers项目地址: https://gitcode.com/GitHub_Trending/te/tech-interview-handbook创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考