读完这篇，你能做什么
能实现边界一致的二分查找，并为重复值与空输入定义正确行为。
学习理由、准备要求与知识点
为什么学它
排序与查找能训练你找出算法运行中保持成立的条件（不变量）、检查边界，也是学习算法题和索引的重要起点。
先读这些内容
知识点清单
- 比较规则与稳定性
- 平方级排序
- 归并排序及空间
- 二分有序前提
- 闭区间不变量
- mid 与边界推进
- 重复值返回合同
- 整体排序加查询成本
运行前先确认Java 17；源码在本机 Microsoft OpenJDK 17.0.20.1 src.zip 核验，在线链接为上游 jdk-17.0.20-ga。深入模块可在掌握基础后回读。
01先弄懂它是什么
排序之前，先说清按什么比较：升序还是降序，空值放哪里，相同分数是否继续比较编号。比较规则必须前后一致，不能出现 a 小于 b、b 小于 c、c 又小于 a 的循环。整数比较别直接用减法返回结果，数字太大可能溢出；使用 Integer.compare 等方法更清楚。
如果两条记录比较相等，稳定排序会保留它们原来的前后关系。例如同分学生原先按报名顺序排列，稳定排序后这个顺序仍能保留；分多轮按字段排序时也可能用到它。稳定说的是相等元素的次序，不表示线程安全。Java17 对对象数组和基本类型数组采用不同的排序实现与规则，不能概括成所有情况都用一种算法。
二分查找依赖按同一比较规则排序的前提。库方法找到相等值时可能返回任意一个匹配位置；如果需要最左位置、最右位置或出现次数，必须定义新的边界问题。左闭右开区间有助于把空区间、全部小于和全部大于统一处理，减少不断打补丁的特殊分支。
文中这几个词，先认一认
- 稳定性
- 排序规则认为相等的元素，排完后仍保持原先的前后关系。
- 下界位置
- 从左往右第一个大于或等于目标的位置；没有时用数组长度表示。
- 上界位置
- 从左往右第一个严格大于目标的位置；没有时用数组长度表示。
- 循环不变量
- 例如逐项求和时，可以要求每轮开始，sum 都等于已经处理过的数字之和。这样在每轮同一检查点都必须保持的规则，能帮助检查漏处理、越界等问题；判断循环能否结束，还要结合循环如何向结束条件推进。
02看看它怎么工作
插入排序维护一个已经有序的前缀，每次把下一个元素插入合适位置，较大的前缀元素向右移动。移动条件使用严格大于时，相等元素不会被越过，因此这种形式可以保持稳定。最坏逆序输入要搬运大量元素，时间平方；但短小或近乎有序区间可能很实用，成熟排序实现也会组合不同策略。
归并排序把两半分别排好再合并，典型比较时间为 O(n log n)，常见数组实现需要额外空间。快速排序通过划分减少子问题，平均性能常好，但最坏情况和具体防护要看实现。堆排序有不同的空间和稳定性取舍。选算法应综合规模、已有顺序、内存和比较成本，而不是只记一个排行榜。
下界二分维护左边都小于目标、右边都不小于目标的事实。中点小于目标时，左边界移到中点后一位；否则把右边界收缩到中点，保留它可能成为第一个合格位置。上界只把比较条件改为小于等于。图中两个边界形成的区间长度，就是重复目标出现的次数。
正在加载流程图…
查看流程图源码（Mermaid）
flowchart TD
A["已按升序排列的数组"] --> B["求首个不小于 target 的位置 L"]
A --> C["求首个大于 target 的位置 R"]
B --> D["相等元素区间为 L 到 R，不含 R"]
C --> D
D --> E["出现次数 R-L"]
D --> F["L 等于 R 表示不存在"]按顺序看，每一步做了什么
- 明确比较器、排序方向与稳定性。
- 说明是否允许修改输入。
- 把查找目标改写成单调边界条件。
- 为区间两侧写出不变量。
- 验证空数组、重复和两端不存在的目标。
03对照实现代码
Microsoft OpenJDK 17.0.20.1；java.base/java/util/DualPivotQuicksort.java · java.util.DualPivotQuicksort#insertionSort(int[],int,int)
以下为原创 Java 17 教学实现，不是原样 JDK 源码；只保留文中明确讨论的机制，省略优化、兼容及内部接口。
public final class SourceModel {
public static void insertionSort(int[] values) {
for (int i = 1; i < values.length; i++) {
int value = values[i], j = i;
// 有序前缀中严格较大的元素后移，给当前值腾出位置。
while (j > 0 && values[j-1] > value) {
values[j] = values[j-1];
j--;
}
values[j] = value;
}
}
}本机 DualPivotQuicksort 包含 int 小区间的 insertionSort 辅助方法，按前缀插入方式移动元素。模型处理整个数组并使用更直观的循环变量，展示这一局部策略，不代表 Arrays.sort 的完整算法；真实排序还会根据区间、数据特征和其它条件选择不同路径。
外层走到 i 时，前 i 个元素已经排好序。先保存当前 value，再把比它大的元素向右搬，最后填进空出的位置，排好序的部分就多一项。若不先保存，搬动时覆盖原位置就会丢掉这个值。这条每轮都成立的规则，同时解释了为什么数据没丢、顺序也正确。
内层使用严格大于，使相等值不会相互跨越。对于 int 数组，看不出相等数值原来的身份，但这个规则推广到带附属字段的元素时与稳定性有关。不能由某个局部插入步骤稳定，就推出包含其它划分步骤的完整原始类型排序具有相同对象稳定契约。
源码选择插入排序处理小区间，说明渐近较差算法仍可能在局部具有价值。阈值和组合策略是具体版本实现细节，调用者应依赖公开排序契约，而不是复制内部阈值到业务代码。性能比较还需考虑输入规模、初始有序度和比较器成本。
代码先调用谁，再调用谁
Arrays.sort的实现路径进入内部排序器- 根据区间条件选择小区间处理
insertionSort维护有序前缀- 返回后由更大排序流程完成整体任务
04动手写一个例子
用两次二分查找重复值的半开区间
对调用者保证升序且计算期间不修改的 int 数组，返回目标值的 [start,end) 下标范围。不存在时两个位置相同；空数组返回 [0,0]。查询不额外扫描验证排序。
- 输入 1
[1,2,2,2,4]，目标2- 输出 1
[1,4]
- 输入 2
[1,3]，目标2- 输出 2
[1,1]
- 输入 3
[]，目标5- 输出 3
[0,0]
下界寻找第一个满足值大于等于目标的位置，上界寻找第一个满足值严格大于目标的位置。两个谓词在升序数组上都从假变真，因此可以使用相同半开区间框架。lo 与 hi 初始为零和长度，hi 本身可以等于数组长度而不被读取。
每轮选择 lo+(hi-lo)/2，保证中点处于尚未确定范围。若当前值仍在谓词为假的左半区域，就把 lo 移到 mid+1；否则保留中点作为可能答案，把 hi 设为 mid。区间长度严格缩小，最终 lo 等于 hi，左右已知区域相接。
将上界减下界得到出现次数，无需在找到任意相等项后向两侧扫描。大量重复值时仍保持对数级查询。排序前提由构建或调用阶段保证，若在每次查询前完整检查有序性，总成本会变成线性；正确文档应同时说明前提与省略的工作。
为什么这样写是对的下界搜索中 [0,lo) 全部小于目标，[hi,n) 全部不小于目标；上界把条件分别替换为不大于和大于。
每次迭代将未确定区间约减半，直到长度为零；不执行排序或全数组有序校验，若需要这些步骤应另计成本。
保存为 Main.java，运行 javac --release 17 -encoding UTF-8 Main.java，再运行 java Main。程序包含固定输入自测，断言失败时会抛出错误。
展开收起代码 · Main.java · 完整可运行程序
长行可在代码区域内左右滚动，按 Tab 可把焦点移入代码区。
import java.util.Arrays;
public class Main {
static int bound(int[] sorted, int target, boolean upper) {
int lo = 0, hi = sorted.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
// 上界越过相等值，下界保留相等值为候选。
if (sorted[mid] < target || (upper && sorted[mid] == target))
lo = mid + 1;
else hi = mid;
}
return lo;
}
static int[] range(int[] sorted, int target) {
if (sorted == null) throw new IllegalArgumentException("sorted");
// 输入升序是前提；这里不增加 O(n) 的重复验证。
return new int[]{bound(sorted,target,false),bound(sorted,target,true)};
}
static void check(int start, int end, int target, int... input) {
if (!Arrays.equals(new int[]{start,end},range(input,target)))
throw new AssertionError(Arrays.toString(input));
}
public static void main(String[] args) {
// 重复值、缺失中间、空、两端和极值边界。
check(1,4,2,1,2,2,2,4);
check(1,1,2,1,3);
check(0,0,5);
check(0,0,0,1,2);
check(2,2,9,1,2);
check(0,3,7,7,7,7);
check(0,1,Integer.MIN_VALUE,Integer.MIN_VALUE,Integer.MAX_VALUE);
System.out.println("PASS 7");
}
}这些特殊情况也要试一试
- 所有值相等时得到完整范围。
- 目标小于全部值时返回零位置。
- 目标大于全部值时返回长度位置。
- 空数组不读取任何元素。
进阶选读 · 可选深入：把答案空间改写成单调判定
场景问题要求最小容量、最短时间或最早满足条件的位置，答案不直接在数组里。
做法建立随候选答案单调变化的可行性谓词，证明真假分界与搜索上下界，再对答案空间二分；注意谓词内部的溢出与成本。
复杂度总成本通常为 O(log R × 判定成本)，R 为答案范围大小。
好处与代价单调性必须证明，若规则会反复真假变化，二分会漏掉合法答案。
05项目里怎么用
业务排序要说明主字段相同时怎么办，例如分数降序后再按创建时间和稳定 ID 排。若只按可能重复的字段排序，数据变化时翻页可能重复或漏项。数据库和 Java 比较器也要使用相同规则，不能假设两端默认的文字排序总是一致。
对只读索引，多次查询前先排序通常有价值；对频繁插入或范围查询，应考虑树、跳表或数据库索引，而不是每次重新排全量数组。排序可能修改输入，对共享集合应决定复制或独占使用，避免一个查询功能意外改变其它模块看到的顺序。
比较器必须稳定且无副作用，不能在比较时访问不断变化的远程值。使用 a-b 比较整数可能溢出，返回错误符号会破坏排序前提。测试除正常排序外，还应覆盖极值、相等项、已排序和逆序输入，并区分库 API 保证与当前实现观察。
容易踩的坑
- 用整数相减实现比较器导致溢出。
- 将任意命中位置当作第一个重复值。
- 半开区间里错误使用 hi=mid-1 漏掉候选。
- 把局部插入排序实现当作 JDK 全部排序算法。
几种做法，怎么选
表格有四列，窄屏可左右滑动查看代价和适用条件。
| 方案 | 优势 | 代价与限制 | 适用条件 |
|---|---|---|---|
| 插入排序 | 短小或近乎有序时直接，常见形式稳定 | 最坏平方时间 | 小区间与教学不变量 |
| 归并排序 | 比较次数界清楚且容易保持稳定 | 数组实现常需额外空间 | 稳定排序与外部归并 |
| 排序后二分 | 重复查询成本低 | 构建排序及更新维护有成本 | 固定或批量更新的有序索引 |
06检验是否读懂了
先自己想、自己写，再展开答案核对。场景题是假设的练习情境；遇到还没学过的内容，可以做完基础后再回来。
先用自己的话解释
01稳定排序具体保留什么？
展开参考答案与推导
它保留比较器认为相等的元素原相对顺序，不表示所有元素位置不变，也不保证并发安全。若需要按多个字段确定唯一顺序，应在比较规则中明确平价策略。
02下界为什么在相等时令 hi=mid？
展开参考答案与推导
因为中点可能正是第一个不小于目标的位置，不能排除它。右边界收缩到 mid 会保留该候选，同时继续检查更左是否还有合格位置。
03二分为何必须依赖单调性？
展开参考答案与推导
只有比较结果能排除一整侧候选，缩小范围才不丢答案。无序数组或非单调谓词不提供这种保证，代码仍可能结束，但结果不再有正确性证明。
换个情况，还会处理吗
01数组有很多重复项，库二分返回中间位置是否错误？
展开参考答案与推导
未必。很多库接口只保证返回某个匹配位置，不保证最左。若业务需要重复区间，应使用下界与上界算法，并按其明确契约测试，不能拿额外要求指责原接口。
02每次查询都排序，复杂度能写 O(log n) 吗？
展开参考答案与推导
不能只报告最后查找步骤。完整查询还包含排序成本，通常高于对数；可以把排序移到构建阶段复用，但要同步处理数据更新和排序前提。
03极值排序出现逆序，先检查什么？
展开参考答案与推导
查看比较器是否返回 a-b，极值相减可能溢出改变符号。使用 Integer.compare 或 Long.compare，并测试最小值、最大值和相等值，确保比较关系满足契约。
写代码试一试
01求目标出现次数
- 输入 / 条件
[1,2,2,4]，目标2- 输出 / 预期
2
提示 上界减下界。
展开参考答案与推导
调用 range 后返回 end-start。不存在时两个边界相同自然得到零，不需要另做线性扫描；保留空数组和全部重复样本验证边界。
02改成降序下界
- 输入 / 条件
[5,3,3,1]，目标3- 输出 / 预期
第一个不大于3的位置1
提示 重新写单调谓词。
展开参考答案与推导
把左侧已知区域定义为大于目标，右侧为不大于目标，比较分支相应反向。不要只交换初始边界，降序需要重新证明每次排除的区域确实不可能成为答案。
03为插入排序保留附属标签
- 输入 / 条件
[(2,A),(1,B),(2,C)]- 输出 / 预期
[(1,B),(2,A),(2,C)]
提示 相等时不越过前项。
展开参考答案与推导
将元素改成带键和标签的记录，只在前项键严格大于当前键时移动。测试两个键为二的标签仍为 A 在 C 前，才能观察稳定性，单独 int 值无法展示身份顺序。
读完之后，独立完成
课后作业：自己做一遍
本篇共 10 道作业，先完成 8 道基础与综合任务，再按前置知识挑战进阶题。其中包含 1 道思维拓展，试着换个条件，看看原来的办法是否还管用。不附参考答案。
能实现边界一致的二分查找，并为重复值与空输入定义正确行为。
本篇重点加练
重点练查找区间与重复值合同，检查算法在无匹配和多匹配时是否仍可解释。
- 闭区间不变量
- 重复值返回合同
重点内容会多练几次。先说清楚怎么做，再试试空数据、出错或条件改变时会发生什么。
先自己做，卡住时记下问题，再回来查。问答题写清“为什么、什么时候适用”；动手题留下输入、输出和运行步骤，方便下次重做。
基础必做
- 作业 01原理问答
记录含分数与到达序号，按分数排序。给出能检验稳定性的输入，并分别计算简单插入排序在已排序与逆序情况下的关键比较和移动。
- 提交内容
- 样本、稳定性合同与计数推导。
- 怎样算完成
- 附属信息用于验证稳定性
- 比较和移动成本分别描述
练到的知识点比较规则与稳定性 · 平方级排序
- 作业 02代码推演
对 [4,1,3,1,2] 画归并排序的分割和合并过程，再说明二分查找若直接作用于原数组需要先满足什么条件。
- 提交内容
- 归并图、空间账本与查找前提。
- 怎样算完成
- 中间存储计入成本
- 排序前提可检查
练到的知识点归并排序及空间 · 二分有序前提
- 作业 03代码推演
为两套二分实现分别采用闭区间与半开区间，写出初始范围、退出条件和合法访问位置；只手推长度 0、1、2 的数组即可。
- 提交内容
- 区间不变量表和最小输入轨迹。
- 怎样算完成
- 边界约定从头到尾一致
- 每轮推进可以复核
练到的知识点闭区间不变量
综合应用
- 作业 04编程实践
实现返回第一个不小于目标的位置的查找，输入有序数组可为空，包含重复值与
int极值；先写循环不变量，再提供每次迭代区间变化记录。- 提交内容
- Java 实现、自写边界及线性参考对照测试、运行证据。
- 怎样算完成
- 每轮严格推进
- 缺失目标合同明确
- 索引计算不越界
练到的知识点闭区间不变量 · mid 与边界推进 · 重复值返回合同
- 作业 05面试场景
接口每次请求都复制并排序一万条数据后做一次二分，自称查询
O(log n)。写出完整成本模型，并比较一次预处理多次查询时的不同前提。- 提交内容
- 成本拆分和方案适用条件。
- 怎样算完成
- 复制排序成本纳入
- 数据更新频率被考虑
练到的知识点比较规则与稳定性 · 重复值返回合同 · 整体排序加查询成本
- 作业 06排错实验
用减法构造比较器处理极值整数，再设计故意不推进边界的二分变体；用有界步数测试定位问题，修复后验证独立参考结果。
- 提交内容
- 失败代码、自写极值/重复/超步数测试与修复记录。
- 怎样算完成
- 实验不会无限循环
- 错误由具体反例支持
- 修复保留合同
练到的知识点比较规则与稳定性 · mid 与边界推进
- 作业 07编程实践
实现有序数组中的最近值查询，目标可能不存在；先规定等距平价、重复元素与空数组的政策，再与线性参考逐例比较。
- 提交内容
- Java 实现、自写极值/重复/无匹配测试与运行证据。
- 怎样算完成
- 循环区间保持明确意义
- 差值计算范围被检查
练到的知识点闭区间不变量 · 重复值返回合同
- 作业 08设计评审
检索接口需求写“返回找到的位置”，输入允许重复。列出任意位置、首次位置和全部范围三种合同对调用方的差异，设计区分测试。
- 提交内容
- 三份合同及重复样本。
- 怎样算完成
- 接口保证与用户需求对应
- 未匹配的表示同样明确
练到的知识点重复值返回合同
进阶挑战 · 掌握前置后选做
- 作业 09设计评审
完成外部存储基础后：数据规模超过可用内存，要求稳定排序并频繁按范围查询。比较外部排序和持久化索引方案，列出内存、磁盘与更新成本。
- 提交内容
- 方案图、资源估算与验收计划。
- 怎样算完成
- 模型包含 I
/O成本 - 数据变更下的索引有效性有合同
- 模型包含 I
练到的知识点归并排序及空间 · 二分有序前提 · 重复值返回合同 · 整体排序加查询成本
思维拓展
先写出你的猜想，再用例子或实验验证。答案可以不同，但要说清依据、适用情况，以及还有什么没弄懂。
- 作业 10思维拓展 · 条件变化
排序数据允许搜索过程中被另一个线程插入，原二分不变量依赖哪些前提？在不实现并发容器的条件下提出可验证读取合同。
- 提交内容
- 交错样本、前提列表和方案比较。
- 怎样算完成
- 静态有序前提被显式审查
- 结果所属时点可以解释
练到的知识点闭区间不变量 · 重复值返回合同
完成后，再检验一次
给每题标记“独立完成 / 查阅后完成 / 尚未完成”。查过资料或没做出的题，记下卡在哪里。隔一天换一组输入再试，能解释结果和出错原因，再把这个知识点标为掌握。
继续阅读
先看能帮你完成当前练习的部分。例子跑通后，再读更深入的解释。
- 必读教程英文
Harvard CS50：算法 （新标签页）↗
阅读线性/二分查找、排序与 O/Ω/Θ，跟随具体输入推导操作次数。
- 实践参考文档英文
Java 17 API：Arrays （新标签页）↗
查阅
copyOf、equals、sort、binarySearch和asList的具体契约。 - 深入参考文档英文
Java 17 API：Comparator （新标签页）↗
阅读 comparing、
thenComparing与排序契约，避免减法比较溢出。 - 实践实践指南中文
Hello 算法：用图和 Java 理解数组、链表与查找 （新标签页）↗
先读第 2 章和第 4—6 章，再读二分查找。小练习：在五个数字的数组中插入一个数，先画出移动过程，再用 Java 实现；说明容量不够时怎么办。 正文和代码公开，部分可视化依赖外部工具。教材支持多种语言，建议先固定 Java 学习。
- 实践实践指南中文
VisuAlgo 排序动画：看清每一次比较和移动 （新标签页）↗
先把右上角切到“探索模式”，选 INS（插入排序）或 MER（归并排序），用“新建(A)”输入六个数字。先手算前三步，再用动画检查；把输入改成倒序后，比较移动或比较次数。 页面公开，部分答案只向教师开放，账号功能另有限制。中文页混有英文。
- 深入参考文档英文
OpenJDK 17u java.util.DualPivotQuicksort （新标签页）↗
定位
DualPivotQuicksort中intinsertionSort的有序前缀移动，仅作为完整排序器的局部策略。 - 深入参考文档英文
Princeton 基础排序 （新标签页）↗
阅读插入排序、比较次数与初始有序度影响。
- 深入参考文档英文
Princeton 归并排序 （新标签页）↗
学习稳定合并、不变量和线性对数复杂度。