企业官网建设流程全解析

可能不少后端同学都有过类似的体验：接口数据量一上来，某些不起眼的代码段就成了瓶颈。我印象比较深的一次，是在处理几十万条有序数据的时候，遇到了一个用 for 循环从头查到尾的实现，单次请求光查目标数据就做了几万次比较。其实这个场景用二分查找，几十次比较就能搞定。可能有人觉得二分查找不就是一个教科书算法吗？但真正手写一遍就会发现，到处都是边界坑。这篇文章就从 Java 的角度，把这个算法从原理讲到工程封装，再把我踩过的坑一并交代清楚。适合刚接触算法的同学打基础，也适合写业务代码多年、遇到二分就"差一错误"的老开发。

1. 二分查找为什么快：先弄懂核心逻辑

1.1 猜数字游戏背后的"减半"思想

如果只用一句话解释二分查找，那就是"猜数字"：我心里想一个 1 到 100 之间的整数，你来猜，每次我告诉你猜大了、猜小了、还是猜中。最高效的策略不是从 1 开始一个一个往上试，而是先猜 50。如果答案是 80，50 猜小了，那答案就落在 51 到 100 之间；再猜 75；再猜 88……每一轮都把可能范围砍掉一半。2 的 6 次方是 64，2 的 7 次方是 128，所以最多 7 次就能在 100 个数里找到答案。

算法做的事和这个游戏一模一样。给定一个有序数组，先看中间位置那个数，跟目标值比一次。这一比，要么命中，要么基本确定目标值只能在左半边或右半边。丢掉另一半之后，继续在新区间里取中间值，重复这个过程。核心机制就是：通过一次比较，把搜索空间砍半。这是它这么快的原因，也是名字里"二分"的由来。

很多人觉得二分查找难，不是因为逻辑复杂，而是因为"砍半"这个动作落实到下标计算上，会产生一堆边界问题。算法思想十分钟就能理解，但把代码写对，尤其是各种变体写对，需要弄清楚区间怎么收缩。后面所有内容都会围绕"区间"两个字展开。

1.2 三个前置条件：不是所有数组都能二分

二分查找能成立，有三个条件需要注意。

第一个条件是有序。无序数组里取中间值来比大小，没有任何信息量，比完也排除不了目标值所在的范围。所以使用二分前必须确认数组已经排序。如果数据是动态增长又频繁查询的，可以考虑用红黑树之类的平衡树结构；如果数据本身不变，排序一次之后反复二分，那就非常划算。

第二个条件是可以随机访问。数组天然满足，因为 arr[mid] 直接按下标取数就是 O(1) 的。链表不行，你拿到 mid 这个"位置号"之后还得从头遍历过去，每轮都要付出 O(n) 的成本，整体复杂度就退化成了 O(n log n)，还不如顺序遍历。Java 里我记得早年的 LinkedList 也提供过类似按索引取值的操作，但内部也是折半遍历，用起来要谨慎。

第三个条件是元素可比。基本类型用 < > == 就行，对象数组需要实现 Comparable，或者在调用时传入一个 Comparator。这一点平时写玩具代码不敏感，但一泛型化就变得特别关键，编译期可能直接报错。我见过不下三次，有人把对象数组直接丢给 Arrays.binarySearch，编译不过，才意识到缺了比较器。

1.3 复杂度对比：100 万数据只需 20 次比较

复杂度这个话题，面试时大概每个人都能说出 O(log n)，但"为什么是 log"这件事，能讲清楚的人少很多。逻辑其实非常朴素：每轮结束，搜索范围从 n 变成 n / 2，再变成 n / 4，一直到剩下最后 1 个元素。如果把"除以 2 的次数"设为 k，那就有 n / 2^k = 1，算出来 k = log2(n)。这就是复杂度里那个 log 的来源。

把数字摆出来更直观。数组长度 100 万时，顺序查最坏要比较 100 万次，二分最多 20 次。1000 万时，顺序最坏 1000 万次，二分最多 24 次。差距是非常大的，尤其是查询次数一多，性能差异就是几个数量级。我做过一个粗糙的本地测试，构造一个 100 万长度的有序 int 数组，用二分和线性遍历各跑若干次查询，二分的单次耗时比线性少了好几个量级，而且数组越大差距越明显。

空间上，迭代版只需要 low、high、mid 三个变量，额外空间 O(1)。递归版每次调用会压栈，深度约 log2(n)，栈空间的代价也不高。不过在 Java 里没有尾递归优化，数据规模极端大的时候迭代版更稳。从工程角度讲，迭代版通常是我更推荐的选择。

2. 手写第一版：Java 迭代二分查找

2.1 十几行代码的基线版本

先写一个最简单的迭代版，先不搞泛型，就查 int 数组。这个版本是所有变体的地基。

public class BinarySearch { public static int binarySearch(int[] arr, int target) { int low = 0; int high = arr.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return -1; } }

这段代码总共也没几行，但已经把一个完整的二分查找闭环了。low 和 high 定义的是当前搜索区间，初始时是 [0, arr.length - 1]。mid 是区间中点。每次把 mid 上的值和 target 比较一次：相等直接返回下标；如果中间值小于 target，说明目标只可能在右半边，low 往上挪；反过来 high 往下挪。区间空了还没找到，就返回 -1。

有一点我想特别强调：while 的条件我写的是 low <= high，不是 low < high。当 low 和 high 指向同一个位置时，这个位置还有一个元素没有被检查过，必须在这个循环里继续判断。如果写成 low < high，恰好目标值落在最后一个元素上，就会漏掉，返回一个错误的 -1。这个细节可以说是二分查找最常见的翻车点。

2.2 最容易出错的三个点：边界、mid、更新规则

先说 mid 的计算。新手最容易写的是 mid = (low + high) / 2。这个写法在数组规模小的时候不会出问题，但一旦 low + high 超过了 int 上限，结果会变成负数，mid 就会变成一个负值，直接拿 arr[mid] 取数必然抛出越界异常。虽然普通业务数据很难大到触发这个问题，但既然有更稳妥的写法，就没有理由保留隐患。标准做法是用 low + (high - low) / 2，先算区间跨度的一半，再加到 low 上，从数学上避开了溢出。也有人用 (low + high) >>> 1 这种无符号右移的做法，同样可以，我之前在源码里见过这种风格，只是可读性稍差，团队里不一定适合普及。

第二个容易错的是更新区间时没有排掉中间位置。arr[mid] < target 的时候，arr[mid] 本身已经可以排除，所以下一轮 low 要从 mid + 1 开始；arr[mid] > target 时，下一轮的 high 要变成 mid - 1。一旦偷懒写成 low = mid 或 high = mid，当区间缩小到只剩一个元素时，mid 会一直等于 low 或者 high，区间收缩不下去，就进入死循环。这个坑我调试过很久，后面第 5 节会展开讲排查过程。

第三个容易错的是"返回值语义"没想清楚。基础二分找不到就返回 -1，这个在"只需要判断存在性"的场景没问题。但工程里更常见的是，要在有序数组里找"第一个 >= target 的位置"，或者"最后一个小于等于 target 的位置"，这时候 -1 完全不够用。JDK 的 Arrays.binarySearch 对找不到的情况返回 -(insertion point) - 1，用负数同时表达"没找到"和"插入点"，这个设计非常巧妙，值得我们在做工具类封装时借鉴。

2.3 实测：和线性查找拉开多少差距

理论说了半天，还是自己跑一下比较踏实。我写了一个简单测试：生成长度 100 万的 int 数组，每个元素等于下标乘以一个常数，保证严格递增。然后分别用线性扫描和二分查找去搜同一个目标值，各执行 100 次查询，统计平均耗时。二分的版本每次最多 20 次比较，线性版本平均要跑到 50 万次比较左右。耗时差距是数量级的，完全符合复杂度的估算。

有个测试细节我觉得值得提一下：这种耗时测试最好把数组初始化放在计时之外，否则分配数组的时间会干扰结果。另外 JIT 预热对结果影响很大，跑几次热身后再统计，比一上来就记时更可靠。我之前用 System.nanoTime 做最简单的统计，为了保证结果稳定，会每个方法连续跑很多次，取中位数或平均值。

当然，性能测试只是建立直觉，不是让你到处赢了线性查找就得意。真正的工程判断还要看数据量、查询频率、缓存友好性、是否已经有序这些因素。如果数据量只有几十条，线性查找反而更简单直接；如果数据可以预处理成哈希表，查询复杂度能到 O(1)，空间代价也你得很清楚。

3. 递归写法与四个高频变体

3.1 递归版虽然优雅，但要注意栈深度

递归版本和迭代版本逻辑完全一样，只是把"更新区间后继续循环"换成了递归调用。

public static int binarySearchRecursive(int[] arr, int target, int low, int high) { if (low > high) { return -1; } int mid = low + (high - low) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { return binarySearchRecursive(arr, target, mid + 1, high); } else { return binarySearchRecursive(arr, target, low, mid - 1); } }

代码更短，结构上也更能体现"分治"的思想。但有几个注意点。第一个是递归出口必须写对，low > high 时区间为空，代表没有找到，返回 -1。第二个是递归调用时同样要保证区间确实在缩小，也就是更新 low 或 high 时必须 +1 / -1，否则无限递归直到栈溢出。第三个是 Java 没有尾递归优化，每次递归都是一次真实的栈帧分配，深度等于 log2(n)，常规数据规模没问题，但如果你处理的是数十亿级以上元素，递归深度也会变大，迭代版更安全。

我的个人习惯是学习阶段用递归，因为它和"分治"思路贴合得很紧，理解起来不绕。生产代码里我更喜欢迭代版，少一点无谓的栈开销，也少一种出错的可能。

3.2 变体一：找第一个等于目标值的下标

前面提到，基础二分遇到重复元素时，"找到的"不一定是"第一个"或"最后一个"。这个问题在真实业务里非常常见。假设有一个成绩数组 [60, 70, 70, 70, 80]，你想知道 70 分开始在哪里，基础二分可能会返回中间任意一个 70 的下标，不够用。

解决思路也很简单：命中 arr[mid] == target 时，不急着返回，把 high 改成 mid - 1，继续在左半边找，同时用 result 保存当前这个命中位置。循环结束后，result 就是最左边的那个 target。

public static int findFirst(int[] arr, int target) { int low = 0; int high = arr.length - 1; int result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { result = mid; high = mid - 1; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return result; }

这个变体是整个"系列问题"的地基。配合一个找最后一个下标的对称实现，你就可以在 O(log n) 时间内统计出一个重复值在有序数组里出现了多少次，方法是最后一个下标减第一个下标再加一。

3.3 变体二：找最后一个等于目标值的下标

对称的问题需要对偶地解决：命中时把 low 挪到 mid + 1，继续往右看，看看还有没有更靠右的 target，同时用 result 记录命中位置。循环结束后 result 就是最右边的目标下标。

public static int findLast(int[] arr, int target) { int low = 0; int high = arr.length - 1; int result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { result = mid; low = mid + 1; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return result; }

这个方向比 findFirst 更容易写反，因为找右边的时候容易顺手把 high 改掉，但实际上是 low 需要右移。建议写之前先在纸上画一个带重复元素的数组，把 low、high、mid 的每一步走一遍，比背代码可靠。

还有一类实现不借助 result 变量，而是直接用 low 或 high 的最终值来收敛。比如标准库风格的双闭区间写法，最后 low 自然停在"第一个大于等于 target"的位置。这类写法更精炼，但对初学者来说直接上最简版本容易晕。我自己的路径是先学会 result 记录法，逻辑完全通透之后再去看那些简洁写法，反而觉得理所当然了。

3.4 变体三：lowerBound 与 upperBound 的用途

这两个变体可能算不上"二分查找"本身，但它是二分思想在算法题和工程里最常用的两个外延。lowerBound 返回数组中第一个大于等于 target 的下标，如果所有元素都小于 target，返回数组长度；upperBound 返回第一个大于 target 的下标，如果所有元素都小于等于 target，也返回数组长度。

public static int lowerBound(int[] arr, int target) { int low = 0; int high = arr.length; while (low < high) { int mid = low + (high - low) / 2; if (arr[mid] < target) { low = mid + 1; } else { high = mid; } } return low; } public static int upperBound(int[] arr, int target) { int low = 0; int high = arr.length; while (low < high) { int mid = low + (high - low) / 2; if (arr[mid] <= target) { low = mid + 1; } else { high = mid; } } return low; }

你注意这两个版本的区间写法和前面不太一样。high 初始化为 arr.length，并且 while 条件用的是 low < high。这种写法把 high 当作开区间，区间语义是 [low, high)，只要 low < high，mid 就一定是有效下标。退出循环后 low 就是我们要的收敛位置。把区间开闭想清楚，这两个函数就没有任何玄学。

实际应用非常广。比如统计某个分数区间 [80, 90) 有多少人，只需要分别求 lowerBound(arr, 80) 和 lowerBound(arr, 90)，或者 upperBound(arr, 79) 和 lowerBound(arr, 90)，下标相减就是人数。想查某个商品价格区间 [100, 200] 里的商品列表同理。

顺便提一句，JDK 的 Arrays.binarySearch 在未命中时返回 -(insertion point) - 1，这个 insertion point 其实就等于 lowerBound 的结果。所以你借助 JDK 也能拿到插入点，不用自己维护一套工具。但理解 lowerBound 的原理仍然有价值，因为很多场景需要精确控制"第一个等于"或"最后一个等于"，这时候 JDK 基础方法满足不了。

4. 封装成工程可用的工具类

4.1 入口参数校验与防御式编程

基础二分代码在"干净"的输入下没有问题，但工程调用没有这么温柔。外部传入 null 数组、空数组、甚至没排序的数组，都是可能的。null 数组不做校验，代码直接抛 NullPointerException 还算好发现；空数组长度是 0，循环一开始 low <= high 就不成立，直接返回 -1，这个看似安全的行为其实也不总符合业务预期，有些场景要求你返回"插入点为 0"。

我的习惯是，在公有方法入口做两层防御。第一层用 Objects.requireNonNull 判空，第二层对 length == 0 做显式处理并写注释，说明为什么返回 -1 或者 0。同时，javadoc 里要写清楚调用方必须保证数组有序，因为二分查找本身没有办法验证数组是否有序——除非先遍历一遍，那就丧失了意义。

团队协作时，方法命名也很重要。直接暴露一个泛泛的 binarySearch 方法，调用方可能不知道"这个方法的返回值碰到重复元素到底是什么意思"。我在项目里更倾向于封装几个语义明确的方法，比如 findFirstIndex、findLastIndex、lowerBound，让调用方按需选择，不默认大家都有一样的脑回路。

4.2 泛型 + 自定义比较器，支持对象数组

只支持 int 肯定不够。项目里经常要按用户 ID 从有序用户列表里查某个用户，或者按时间戳从有序日志里定位某条日志。这时候需要的不是 int 版本，而是一个能处理对象数组的泛型版本。

public static <T> int binarySearch(T[] arr, T target, Comparator<? super T> cmp) { Objects.requireNonNull(arr, "arr is null"); Objects.requireNonNull(cmp, "comparator is null"); int low = 0; int high = arr.length - 1; while (low <= high) { int mid = low + (high - low) / 2; int c = cmp.compare(arr[mid], target); if (c == 0) { return mid; } else if (c < 0) { low = mid + 1; } else { high = mid - 1; } } return -1; }

泛型签名里的 Comparator<? super T> 是很多初学者绕不清的点。它表达的意思是：这个比较器既可以比较 T 本身，也可以比较 T 的某个父类型。Java 泛型在设计上对"逆变"有严格的约束，写成 Comparator 也能编译，但灵活性差很多。实际写工具类时，用 ? super T 是最标准的姿势。

对象数组场景还有一个容易踩的坑：排序和查找必须使用同一个比较器。如果排序时按时间排序，查找时却误用了按 ID 排序的比较器，二分查找的整个前提就被破坏了，结果自然是乱猜。这种问题在代码审查里非常隐蔽，因为代码本身不报错，只有查询结果产出期不稳定。

4.3 和 JDK 自带 binarySearch 的取舍

既然 JDK 已经提供了 Arrays.binarySearch，自己写一套还有意义吗？我的判断是：生产环境能用 JDK 的优先用 JDK，它经过大规模测试和多年维护，稳定性和性能都有保障。但这不代表不需要理解手写实现，更不代表手写版本没有存在价值。

有几个场景必须自己动手。一是需要"第一个等于"或"最后一个等于"时，JDK 的 binarySearch 不保证返回哪一个重复元素的下标，语义不够精确。二是需要同时获得插入点信息做范围查询时，虽然 JDK 返回值里能还原插入点，但代码可读性不如一个明确的 lowerBound 方法直白。

JDK 返回值的设计我还是想专门夸一下。找不到时返回 -(insertion point) - 1，这个负数既不是合法下标，又能通过简单公式还原插入位置：

int idx = Arrays.binarySearch(arr, key); if (idx >= 0) { // 找到了 } else { int insertionPoint = -idx - 1; // 没找到，插入到 insertionPoint 可保持有序 }

这套语义被很多框架和方法沿用。自己封装工具类时，保持同样的语义也能降低团队的学习成本——大家看到返回值规律就明白，不用重新学一套约定。

5. 实战踩坑记录与高频问题速查

5.1 死循环和溢出的现场复盘

写二分查找，最难调的 bug 不是结果错，而是死循环。有一次我在一个变体实现里把 low = mid + 1 写成了 low = mid，数组长度恰好在某些边界条件下会触发死循环。可怕的是，它不是每次必现，有些数据能跑过，有些数据一头扎进循环里出不来。最后通过在循环里打印 low、mid、high，发现 mid 一直停在同一个位置，low 永远追不上，才定位到问题。

这类问题有规律可循：当 low 和 mid 相等时，如果某个分支没有让 low 前进，就会原地打转。经验是写完二分后，至少人工检查两种极端输入：区间只剩一个元素，即 low == high；区间只剩两个元素，即 low == high - 1。把这两个场景走通，大部分死循环问题都能暴露。

mid 溢出也是我在项目里见过的隐患。原代码写着 (low + high) / 2，当时数据量没有大到触发溢出，但这个地雷一直埋着。后来做代码规范时统一改成了 low + (high - low) / 2，成本几乎为零，却消除了整个隐患。我建议看到这种写法就顺手改掉，不要等到大数据场景爆炸再后悔。

5.2 重复元素场景下的"玄学结果"

另一个典型的线上问题是：结果"随机波动"。核心原因往往是有人在重复元素数组上直接用了不保证命中位置的二分方法，然后拿返回的下标去取数组里的其他信息。比如两个相同 ID 的用户，基础二分查出来有时是第一个，有时是最后一个，取到的用户信息就不一致，统计结果自然忽对忽错。

这类问题的本质是"找到一个"和"找到哪一个"的语义冲突。只要数据可能重复，调用方就必须明确预期语义。我在团队工具集里会刻意只保留 findFirst、findLast、lowerBound、upperBound 几个语义明确的方法，让调用方自己选定。底层那个"返回任意命中下标"的方法反而不建议暴露出去，因为默认语义就是含糊的，容易背锅。

5.3 二分查找常见问题速查表

我把高频问题整理成一张表，方便写代码时对照排查。

这张表看着简单，但每一条后面都有真实场景支撑。遇到二分相关的问题，先别怀疑算法原理，绝大多数情况就是某个边界点没处理干净。

最后说一个我自己坚持了很久的习惯：写二分的时候，不要默认"数组里一定有这个数"，要把"找不到"当成正常路径来处理，而不是抛异常。工程里用二分查配置、查日志、查用户数据，很多本来就是"可能不存在"的查询。一上来就把找不到当异常处理，很容易在生产环境制造一堆没必要的告警。写完代码以后，低边界（low == high）、重复元素、完全找不到这三类输入都多测几遍，比背下各种写法都更管用。