从一道图论题，挖出 Java Collections.binarySearch 的底层设计美学

今天在做力扣的时候有个小发现 缘起一道被排序数组简化的图论题题目是这样的有 n个节点编号 0 到 n - 1和一个按非递减顺序排序的数组nums以及一个阈值maxDiff。如果|nums[i] - nums[j]| maxDiff则节点 i和j连通。现给出多次查询queries [u, v]问节点u和v是否连通这是一道非常经典的图论连通性判断题。如果没有“数组已排序”这个条件我们通常需要用到并查集Union-Find或广度优先搜索BFS。但因为数组是有序的整个图的结构实际上变成了一条直线。如果两个节点连通它们必定属于同一个连续的“区间”。 常规解法数组打标签最直观的想法是线性遍历只要相邻元素差值nums[i] - nums[i-1] maxDiff就说明图在这里“断开”了进入了一个新的连通块。我们可以开辟一个长度为n的数组遍历一次给每个节点打上“连通分量 ID”。后续的查询只需要 O(1)的时间比对 ID 即可。public class PathChecker { public ListBoolean hasPath(int n, int[] nums, int maxDiff, int[][] queries) { int[] components new int[n]; int currentComponentId 0; for (int i 1; i n; i) { if (nums[i] - nums[i - 1] maxDiff) { currentComponentId; } components[i] currentComponentId; } ListBoolean answer new ArrayList(); for (int[] query : queries) { int u query[0]; int v query[1]; answer.add(components[u] components[v]); } return answer; } }这种做法时间复杂度 O(n q)空间复杂度 O(n)非常标准且高效。 进阶空间换时间的区间映射法接下来我们来看一种灵神的精妙解法寻找“间断点”。Javaclass Solution { public boolean[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) { // 1. 收集所有“间断点”的索引 ListInteger idx new ArrayList(); for (int i 0; i n - 1; i) { if (nums[i 1] - nums[i] maxDiff) { idx.add(i); } } // 2. 处理查询 boolean[] ans new boolean[queries.length]; for (int i 0; i queries.length; i) { int[] q queries[i]; ans[i] binarySearch(idx, q[0]) binarySearch(idx, q[1]); } return ans; } private int binarySearch(ListInteger idx, int target) { int i Collections.binarySearch(idx, target); return i 0 ? ~i : i; // 这一行是灵魂 } }它的核心思想是既然断点很少我们就只把这些断点存进idx列表里。这些断点把整个节点集切分成了若干个闭区间。对于任何一个查询节点target我们只需要在idx中二分查找它属于哪个区间。只要两个节点落在了同一个区间即它们的“插入点”相同它们就是连通的这个解法将空间复杂度从 $O(n)$ 降到了 $O(k)$$k$ 为间断点数量代价是查询时间变成了 $O(q \log k)$。但这段代码中最让人拍案叫绝也最让初学者摸不着头脑的是那个神秘的二分查找包装函数return i 0 ? ~i : i;️‍♂️ 深挖Collections.binarySearch的防翻车设计为什么Collections.binarySearch不直接返回我们需要的结果非要我们用按位取反~Bitwise NOT来处理呢这就涉及到了 API 设计中的一个核心矛盾如何用一个int返回值同时表达“状态”和“位置”当我们调用二分查找时我们需要知道两件事找到了吗位置在哪如果找到了返回真实索引如果没找到返回它应该被插入的索引这对于维护有序列表极具价值第一次尝试用正负号区分直觉上我们可以这样设计找到了返回正数索引0, 1, 2...没找到返回负的插入点-插入点致命漏洞出现了遇到“0”就翻车假设列表是[10, 20, 30]我们要查找数字5。5比所有数字都小所以它的插入点是0。按照我们的设计没找到应该返回-0。但在计算机和数学中-0就是0当 API 返回0时调用者陷入了不可调和的歧义到底是我找到了元素10索引 0还是我没找到元素5你需要把它插在索引 0 的位置JDK 设计者的完美解法整体偏移减一为了彻底避开0的歧义Java 的设计者制定了一个绝妙的规则对于所有“没找到”的情况返回值统一向负数方向偏移一位。即返回值 -插入点 - 1让我们重测刚才的极端情况查找5插入点为0返回值变成了-0 - 1 -1。现在整个返回值体系泾渭分明 0一定找到了这就是真实索引。 0一定没找到。返回-1代表插入点是0返回-2代表插入点是1以此类推。为什么是~i数学与位运算的巧合作为调用者当你拿到了i -插入点 - 1这个负数时想要提取出真实的插入点你需要做数学逆运算插入点 -i - 1而在计算机底层的二进制补码表示法中对一个数字求负并减一-x - 1在电路上完美等同于对它进行按位取反~x所以那行神秘的代码return i 0 ? ~i : i;翻译成大白话就是“如果找到了i 0就直接用这个索引如果没找到i 0就把这个负数按位取反还原成它本该待在的插入点。”结语从一道图论连通性判断题到利用空间换取时间的区间切分思想再到利用补码特性优雅还原二分查找插入点的一行代码。我们看到了算法思维的灵活转变也窥见了 JDK 源码底层对于信息复用和消除歧义的极致追求。下次当你再写出~i的时候也许你会想起这背后精巧的数学魔法。