二分、排序与选择

• 两种区间的维护方式与循环不变量差异
• 中值取法 mid 与区间收缩的对应关系
• 死循环（l 不再增大）与越界（r 出界）的根因

左闭右闭 [l,r]：l=0, r=n-1，while(l<=r)，mid=(l+r)/2。若 a[mid]<target 则 l=mid+1，否则 r=mid-1。循环结束时 l>r，l 为 insertion point。左闭右开 [l,r)：l=0, r=n，while(l<r)，mid=(l+r)/2。若 a[mid]<target 则 l=mid+1，否则 r=mid。循环结束时 l==r，即第一个≥target 的位置（lower_bound）。统一记忆法：① 始终让"可行域"保持区间不变式，[l,r) 中 r 是"开"的，所以 r=mid 不排除 mid 本身；② 计算 mid 时用 mid=l+(r-l)/2 防溢出；③ 左闭右开中当 l+1==r 时 mid==l，若进入"l=mid"分支会死循环，故必须写 l=mid+1（或 r=mid）。死循环根因：更新时把 l 或 r 赋成 mid 而非 mid±1，导致区间长度不缩。越界根因：左闭右开把 r 初始化为 n 后，若访问 a[r] 会越界；或左闭右闭 r 初始化为 n 而非 n-1。

两种模板本质是同一逻辑，只是"开区间端点"的包容语义不同。左闭右闭强调 while(l<=r) 且两端都收缩；左闭右开强调 while(l<r) 且 r=mid 不收缩该点。统一记忆的关键是"不变式"——每次循环后搜索区间仍满足[l,r)性质，且 mid 的归属决定 l 或 r 的赋值。防溢出 mid=l+(r-l)/2 是高频考点。

• 四种解法各自的复杂度（平均/最坏）、空间
• 数据规模（K 与 n 的关系）与内存约束下的取舍
• 数据分布（整数可计数、大对象、流式）对选型的影响

① 全排序：全部排序后取前 K，O(n log n)，空间 O(1)（原地）或 O(n)；适合 n 很小。② 大小为 K 的小顶堆（若找前 K 大）：维护堆顶为当前第 K 大，O(n log K) 时间、O(K) 空间；适合"n 巨大、K 较小、只需一次遍历"的流式场景，且不要求修改原数组。③ 快速选择（QuickSelect）：平均 O(n)、最坏 O(n²)，空间 O(log n)（递归栈）；适合 n 很大且 K 随机、内存充足、可原地修改数组的场景，是"单次求前 K"的最优平均方案。④ 计数分桶：若元素是整数且值域有限（如 0..M），用桶计数 O(n+M) 时间、O(M) 空间；适合值域小且元素可为负需偏移，是"数据整型且值域紧凑"时的线性方案。选型原则：K 很小→堆；n 很大且 K 不小→快速选择；整数且值域小→计数分桶；数据流式/无法一次性载入→堆（可配合外部排序）；n 很小→全排序最简单。

四种方案本质是"排序-截断"、"堆式维护"、"部分排序"、"值域映射"四种思路。堆与快速选择在"K 相对 n"不同时各有优劣：堆对 K 敏感（log K），快速选择对 K 不敏感（遍历 n 即可，但需要全量数组）。内存约束是决定性因素：快速选择需 O(n) 随机访问数组，流式或超大 n 只能堆或外部排序。计数分桶是特例，仅当值域结构化时可用。

• 快速排序 partition 与递归结构
• 随机化基准解决"已有序数组"导致的 O(n²) 退化
• 三路切分解决"大量重复元素"导致的退化

随机化基准：partition 枢轴随机选取，使得对"已有序/逆序"等最坏输入，任一片段被选为枢轴的概率均等，从而把最坏 O(n²) 的概率降为极小，期望 O(n log n)。三路切分（荷兰国旗）：把数组分成 <pivot、=pivot、>pivot 三段，递归只处理小于与大于两段。当存在大量重复元素时，普通快排的 partition 会把相等的元素反复划分，造成 O(n²)；三路切分把相等的元素一次性归位，递归规模显著缩小，对全等数组到达 O(n)。三路切分本身也常配合随机化。

两个优化针对不同退化源：随机化针对"基准选取不佳"（有序输入），单调/重复输入仍可能退化；三路切分针对"元素重复"（全等输入），把重复段整体排除。工程上常用"随机化 + 三路切分 + 小数组插入排序兜底"的组合来兼顾最坏与常数因子。

• 旋转数组的性质：某半边必有序
• 用 nums[mid] 与 nums[r]（或 nums[l]）比较判断有序半边
• 重复元素时无法判断有序半边的退化与 while 触发式处理

求最小值：比较 nums[mid] 与 nums[r]。若 nums[mid]>nums[r]，说明最小值在右半（mid 排除），l=mid+1；否则最小值在左半含 mid，r=mid。无重复时 O(log n)。求目标值：先判断哪半边有序，再判断 target 是否落在有序半边内，据此收缩。若 nums[mid]==nums[l]（重复元素），无法判断哪半边有序，只能 l++ 收缩（或 r--），最坏退化为 O(n)。重复元素处理：当 nums[l]==nums[mid]==nums[r] 时无法判断，只能线性收缩，故最坏 O(n)。

核心是"旋转后至少一半有序"，利用它与 target 或边界比较来收缩。重复元素时，nums[l]==nums[mid]==nums[r] 这种"三相等"打破了可判断性，只能逐位收缩，这是复杂度从 O(log n) 退化到 O(n) 的根因。

• 把中位数转化为"前 k 个元素的分割"问题
• 二分较短数组作为分割点，推导另一数组分割点
• 奇偶长度与边界（i=0/j=0/i=m/j=n）的统一处理

设两数组 A（长 m）、B（长 n），假设 m≤n。把问题转化为：在 A 中分割 i、B 中分割 j，使 A[0..i-1] 与 B[0..j-1] 是左半部分，且 i+j = (m+n+1)/2（左半比右半多 0 或 1 个）。对 A 二分 i，则 j=(m+n+1)/2 − i 自动确定。满足 A[i-1]≤B[j] 且 B[j-1]≤A[i] 即为合法分割，中位数 = 左半最大（odd）或 (左半最大+右半最小)/2（even）。边界：i=0 时左半最大取 B[j-1]；i=m 时右半最小取 B[j]；j=0/j=n 同理。因二分对象是短数组 m，故 O(log m)=O(log min(m,n))。

关键洞察是"中位数等价于把有序合并序列切成左右两半"，而分割点由 i+j 唯一确定，故只需二分一个数组。边界处理本质是处理"分割点落在数组端点"的极端情况，通过条件判断避免越界。二分短数组是优化核心，保证 log 底的规模最小。

• 摩尔投票的候选者+计数器思想
• 抵消策略的正确性：超过一半的元素必然在抵消后仍幸存
• 第二遍扫描的原因：候选者未必真超过一半

摩尔投票：维护候选者 cand 与计数器 count。遍历时若 count==0 则 cand=当前元素并 count=1；否则若当前元素==cand 则 count++，否则 count--。正确性：把"多数元素"与"其他所有元素"配对抵消，多数元素出现次数>n/2，故抵消完后必定剩余，幸存者必是多数元素。但仅当题目保证存在多数元素时才成立；若不确定，需第二遍扫描统计候选者真实出现次数，若>n/2 才返回，否则无多数元素。O(n) 时间来自一次遍历，O(1) 空间来自只用一个候选者与一个计数器，不依赖哈希表。

抵消策略的直观理解是"反对票"——把候选者当作一个派别，其他元素对候选者投反对票，多数派因人数优势最终胜出。第二遍扫描是工程严谨性：候选者可能只是"两两抵消后幸存"，但未必超过一半（例如 [1,2,3] 中 3 幸存但只有 1/3）。O(n)/O(1) 是该方法相对哈希表（O(n) 空间）的核心优势。

• 三种方案的时间/空间复杂度
• 平均 vs 最坏复杂度的差异
• 适用场景（流式、单次、严格最坏）

堆：维护大小 K 的小顶堆，O(n log K) 时间、O(K) 空间；适合流式数据、K 较小、不要求改数组。快速选择：平均 O(n)、最坏 O(n²)、空间 O(log n)；适合单次求 Top-K、n 大、允许原地修改、内存充足，是平均意义下最快。BFPRT（中位数的中位数选 pivot）：保证最坏 O(n)，常数因子大、实现复杂；适合需要严格最坏时间界、n 极大且数据不可重排的场景。适用场景：一般工程用快速选择（平均快）；数据流或 K 极小用堆；需要可证明的最坏界用 BFPRT。

三者的本质差异是"数学上最坏"与"实际平均"的取舍。堆交换次数多但稳定地 O(n log K)；快速选择平均极快但可能有 O(n²) 的坏输入；BFPRT 通过精心选 pivot 消除最坏，但常数大。工程上快速选择最常用，因为随机化后 O(n²) 概率极低。

• 稳定排序的定义
• 堆排序长距离交换破坏稳定性
• 堆排序三阶段复杂度分析

稳定性：堆排序不稳定，因为堆顶元素与堆尾元素交换是"长距离跳跃"，相等元素的相对顺序无法保持。建堆（heapify）与堆顶调整过程中，相等的元素可能因为堆的 sift-down 调整而跨越彼此，破坏相对次序。复杂度：建堆 O(n)（自底向上 heapify），堆顶出堆需 n 次，每次堆顶下沉为 O(log n)，故排序阶段 O(n log n)；总复杂度无论输入如何都是 O(n log n)（最好/平均/最坏相同），因为堆的构建与反复 sift-down 不依赖初始有序性。空间 O(1)（原地）。

"不稳定"的根源是堆的物理结构（完全二叉树数组）与调整方式（父子交换）天然跨越任意距离，无法像归并那样按段合并保持相等元素次序。复杂度三阶段相同源于堆排序的对称性：每次堆顶调整都是 O(log n) 的固定成本，与输入数据是否有序无关。

• 分组取中位数、再取中位数之选中位数的 pivot 选择
• 通过 pivot 保证每次划分至少排除固定比例
• 递推式 T(n)=T(n/5)+T(7n/10)+O(n) 的推导

BFPRT 步骤：① 把 n 个元素每 5 个一组，不足 5 个也成一组；② 每组内排序取中位数（O(1) 每组）；③ 递归调用 BFPRT 求这些中位数的中位数 pivot（约 n/5 个中位数，递归规模 n/5）；④ 用 pivot 做 partition；⑤ 判断 pivot 位置，若不在目标侧则递归一侧。关键性质：pivot 至少大于等于约 3/10 的元素、小于等于约 3/10 的元素（因每组中位数的一半占 3 个以上，取中位数的中位数后，至少一半组的 3 个元素在 pivot 一侧）。故每次划分至少排除约 3n/10，递归规模至多 7n/10。递推 T(n)≤T(n/5)+T(7n/10)+O(n)，解得 T(n)=O(n)（因为 (1/5+7/10)=9/10<1）。

核心是"中位数的中位数"保证 pivot 足够"居中"，即左右两侧都至少包含固定比例的元素，从而无论递归哪一侧规模都 ≤7n/10。配合每组 5 个（常数代价取中位数）与递归规模 n/5，递推式系数和 9/10<1 使总复杂度线性。这是"最坏线性选择"的经典证明。

• 无重复时 O(log n) 的判定条件
• 重复元素使有序半边无法唯一判断
• nums[l]==nums[mid]==nums[r] 时的线性收缩

无重复元素时，比较 nums[mid] 与 nums[l]（或 nums[r]）能唯一确定哪半边有序，故 O(log n)。当存在重复元素时，可能出现 nums[l]==nums[mid]==nums[r] 三相等，此时无法判断最小值在左半还是右半，二分对半收缩失效，只能 l++（或 r--）逐位收缩。最坏情况（如大量相等元素环绕）每次仅收缩一个位置，复杂度退化为 O(n)。实现时，当遇到 nums[l]==nums[mid]==nums[r] 三相等时无法判断有序半边，只能改走逐位收缩分支（l++ 或 r--）来保证正确性。

退化根因是"二分依赖可比较性"，而三相等破坏了半边有序性的可判定。工程上为安全，遇到三相等时线性收缩，正确性保留但复杂度退化。这是"旋转数组 + 重复"两道题的核心差异。

• 退化条件：已有序/逆序/全等导致划分极度不均
• 三取样取中位数作 pivot 降低极端输入
• 双轴快排一次划分分三区、插入排序兜底小数组

退化条件：当输入已有序或逆序，且取固定 pivot（如首元素）时，每次划分只有一侧少一个元素，递归深度 O(n)，总 O(n²)；全等元素使普通 partition 也不均。优化：① 三取样取中（median-of-three）：取首、中、尾三个元素的中位数作 pivot，避免极端输入，降低 O(n²) 概率；② 双轴快排（Dual-Pivot，Java Arrays.sort 用）：选两个 pivot 一次划分成 <p1、p1~p2、>p2 三区，减少比较与交换次数，实测更快；③ 插入排序兜底：当子数组长度小于阈值（如 7）时改用插入排序，避免递归开销，因插入排序对小数组有极小常数。三者叠加把最坏概率降到极低并改善常数。

退化本质是划分失衡。三取样与随机化异曲同工，都是降低"坏 pivot"概率；双轴快排重在减少常数；插入排序兜底消除递归底层开销。这是生产级快排（如 Java/C 标准库）的实际组合。

• 最坏情况 O(n²) 的成因
• 三数取中/随机化对"坏 pivot"的缓解
• 双轴快排的常数优化

最坏情况：pivot 选出的是极值（如已有序数组取首元素），每次划分一侧为空，递归深度 O(n)，总 O(n²)。优化：① 随机化：pivot 随机取，任何输入的坏概率被均匀化，期望 O(n log n)，工程上最常用；② 三数取中：取首中尾中位数，提升 pivot 质量，避免常见的"已有序/逆序"最坏输入；③ 双轴快排：两个 pivot 一次划分成三区，虽然算法复杂度仍 O(n log n)，但减少元素移动与比较次数，常数更小，是 Java 对原生类型排序采用的原因。三者都不改最坏上界，但都显著降低坏输入概率或常数。

这里强调"随机化"与"三数取中"是同层优化（都提升 pivot 质量），双轴快排是常数优化。理解"最坏 O(n²) 无法根治，但概率可压到指数级小"是关键。

• 二分答案的前提：判定函数单调
• 把"最小化最大值/最大化最小值"转化为"给定值是否可行"
• 判定函数与二分边界的设计

二分答案框架：当问题目标（如最大最小化、最小最大化、某个阈值）满足单调性——即"若 x 可行则所有 ≥x（或 ≤x）也可行"——时，可以二分答案 x，用 O(判定) 的可行性检查（check(x)）替代直接搜索。常见场景：最大化最小值（如分配工作、行驶距离）、最小化最大值（如切分数组、页面分配）、求最小的满足条件的值。步骤：① 确定答案的单调区间 [lo, hi]；② 二分 mid，调用 check(mid) 判断是否可行；③ 按单调性收缩 lo/hi。复杂度 O(log(区间长度) × check 复杂度)。monotonic 是前提：若判定函数不单调，二分无法保证收敛到正确解。

"二分答案"本质是把"在所有可行解中求最优"转化为"给定阈值判断是否可行"的二分搜索。关键在 check 函数设计（常为贪心或模拟）和单调性证明。这是把看似无解的最优化问题套上二分框架的通用技巧。

• lower_bound 与 upper_bound 的语义
• 左闭右开模板下统一写法
• 用 lower_bound 派生 upper_bound

左闭右开 [l,r) 统一写法：lower_bound 返回第一个满足 a[mid]≥target 的位置，upper_bound 返回第一个满足 a[mid]>target 的位置。核心差异只在分支条件：lower_bound 用 if(a[mid]<target) l=mid+1 else r=mid；upper_bound 用 if(a[mid]<=target) l=mid+1 else r=mid。即 upper_bound 等价于对 target+1 调 lower_bound（仅当整数）。统一记忆：让"不满足条件"的元素全归 l 侧（l=mid+1 排除），"满足条件"的元素归 r 侧（r=mid 保留），循环结束 l==r 即第一个满足条件的下标。若用左闭右闭 [l,r]，则需在循环后判断 l 是否越界。

统一写法的关键是把"满足条件的保留在 r 侧、不满足的排除到 l 侧"，只改比较符号即可在 lower/upper 间切换。这个模板同时解决"查找第一个/最后一个满足条件"的边界问题，是面试高频默写。

• 逆序对定义与归并统计逻辑
• 合并时右半元素小于左半时的计数
• 树状数组替代方案与复杂度

归并排序计数：在合并两个有序子数组时，当把右半的某个元素 a[j] 放入结果时，若左半当前还有 l 个元素未放（即左半剩余元素都大于 a[j]），则这些元素与 a[j] 构成逆序对，累加 l。这样每个逆序对被恰好在跨越左右半的合并中统计一次。总复杂度 O(n log n)。树状数组替代：按值域建 BIT，从左到右遍历原数组，对每个元素 x，查"已出现且大于 x 的个数"= 已插入总数 − 已插入且 ≤x 的个数，累加后把 x 插入 BIT。复杂度 O(n log V)，V 为值域，可先离散化。两种方案都 O(n log n)，归并自然稳定且原地，树状数组更简单编码但需值域处理。

归并计数利用"合并时左右已各自有序"的性质，把跨半逆序对一次性统计，避免逐对比较。树状数组是"在线统计"思路，用前缀和快速查询已出现的大于当前值的元素个数。两者复杂度等价，选择取决于编码习惯与是否需离散化。

• 随机化选择算法的期望复杂度分析
• 最坏 O(n²) 的触发条件与概率
• 与 BFPRT 的对比

RANDOMIZED-SELECT：随机选 pivot 做 partition 后，只递归处理包含目标秩的那一侧（区分于快排需要递归两侧）。期望复杂度 E[T(n)]=O(n)：因为随机 pivot 平均能缩小组，递推期望 E[T(n)]≤E[T(9n/10)]+O(n)，解得 O(n)。最坏 O(n²)：当每次随机 pivot 恰好是最值，一侧为空，递归只缩小 1 个元素，需 n 次递归，总 O(n²)。但该最坏输入概率随随机化极低（指数级小），工程上几乎不可能触发。与 BFPRT 对比：BFPRT 用确定的"中位数之选中位数"保证最坏 O(n) 但常数大；RANDOMIZED-SELECT 期望 O(n)、常数小、最坏 O(n²) 概率极低。

关键区别是"只递归一侧"——这是选择算法比快排（两侧都递归）平均更快的原因。期望分析用"随机 pivot 至少在前 1/10 到 9/10 区间"保证规模收缩，从而线性。最坏 O(n²) 是低概率事件，实际选型常在随机快速选择（期望线性）与 BFPRT（最坏线性但常数大）间权衡。

• 稳定排序的定义与归并的稳定性来源
• 外部排序的"分块-归并"框架
• 归并对外存顺序读写友好

稳定性：归并排序在合并时，当两半元素相等时优先取左半（前半）的元素，相等元素的相对顺序得以保持，因而是稳定排序。外部排序：当数据量远超内存（如 TB 级），无法整体排序，采用"归并"思想——① 把数据切分成若干能装入内存的块，每块内部排序后写回磁盘（生成有序 run）；② 用 k 路归并（配合败者树/锦标赛加速）把多个有序 run 归并成更少更大的 run，直至全部有序。归并思想胜出是因为：归并只依赖顺序读写（磁带/磁盘友好），且归并模式可扩展到任意规模的多路归并，无需全部数据驻留内存。

稳定性源于"相等时取左半"的合并策略，这是归并独有的特性（堆排序、快排都难做到）。外部排序首选归并的核心是"归并的顺序访问特性 + 可分块多路"，使得内存约束下仍能渐进地完成排序，这是经典外部排序（如数据库中的 k-way merge、外存归并排序）的理论基础。

• 两种建堆方式：逐个插入 vs 自底向上 sift-down
• 自底向上建堆 O(n) 的证明
• 自顶向下逐个插入 O(n log n)

自顶向下建堆：从空堆开始逐个插入，每次插入 sift-up 最坏 O(log n)，共 O(n log n)。自底向上建堆：从最后一个非叶节点（n/2−1）开始逆序执行 sift-down，每个节点下沉到合适位置。复杂度 O(n)：因为每层节点下沉距离=该层到堆底的高度，对所有节点求和 Σ(h 层的高度)，可证明为 O(n)。直观证明：第 k 层（从根 0 开始）有 2^k 个节点，每个下沉至多 h−k 步，总代价 Σ_k 2^k·(h−k) = O(2^h) = O(n)。而自顶向下最坏每个节点上升 O(log n)。故自底向上更优。

差异本质是"节点下沉总距离"与"节点上升总距离"的摊还：自底向上时多数节点自身高度小，下沉距离也小，总代价是 O(n)；自顶向下时每个新节点都可能从叶升到根，代价 O(log n) 每个。heapify 的 O(n) 是堆的经典结论，也是堆排序总 O(n log n) 中建堆只占 O(n) 的依据。

• 寻找第一个满足条件（lower_bound）的收缩
• 寻找最后一个满足条件的收缩
• 防死循环与越界处理

求第一个满足条件的位置（如第一个≥target）：左闭右开模板，if(a[mid] 不满足) l=mid+1 else r=mid，返回 l。求最后一个满足条件的位置（如最后一个≤target）：可从 upper_bound(target)−1 得到，即先求第一个>target 的位置再减 1。若需直接写：维护"已确认满足的最大下标"，用 if(a[mid] 满足) {ans=mid; l=mid+1} else r=mid−1。关键差异：找第一个时"满足"收缩右边界（r=mid），找最后一个时"满足"收缩左边界（l=mid+1，并记录 ans），避免死循环。越界处理：返回前检查 l 或 ans 是否在 [0,n) 内。

两个方向的本质是"满足条件时把哪一侧端点拉向 mid"。找第一个：满足→r=mid（保留 mid 可能）；不满足→l=mid+1。找最后一个：满足→l=mid+1（区间右移，且记录）；不满足→r=mid−1。统一用"不满足排除、满足保留"的对称思想，配合 ans 记录可避免死循环。

• 三种排序的线性时间前提（非比较排序）
• 各排序的稳定性来源
• 比较排序下界 Ω(n log n) 与线性排序的突破

计数排序：值域 [0,k] 时用计数数组统计频次、前缀和求位置，再按原序放置，O(n+k)，稳定（放置时从后往前扫描保证稳定）。基数排序：按位从低位到高位多次计数排序，O(d(n+k))，d 为位数，稳定（每次计数排序稳定且低位先排）。桶排序：把元素按区间分桶，桶内排序后按序拼接，当元素均匀分布时期望 O(n)，稳定取决于桶内排序是否稳定。这些属于"非比较排序"，突破比较排序下界 Ω(n log n)，因为比较排序的决策树模型限制任何比较算法至少 Ω(n log n)。稳定性证明：计数排序反向扫描保证相同值的元素保持原相对顺序；基数排序依赖每轮稳定的低位排序使高位相同时低位顺序得以保留。

线性排序的突破点在"利用值域/位结构而非两两比较"，因而绕过决策树下界。稳定性是"按关键字多轮排序"的关键：基数排序的正确性正依赖低位的稳定排序，否则高位的次序会破坏低位已排好的顺序。三者复杂度都含值域/位数/桶数参数，并非无条件线性。