Java Arrays.binarySearch()返回负数的情况解释

今天在刷算法的时候，需要用到二分查找，我自己写完了二分查找的代码并提交通过后，我在题解中发现别人用了 Java 库中的 Arrays.binarySearch 方法来实现二分查找，于是我尝试也调用了这个函数，但是运行发现结果会返回负数，欸，二分返回的结果不是必然是在数组长度范围内么？ 我感到差异，于是乎然后我仔细核对别人的代码，发现代码中出现了如下判断：

int m = Arrays.binarySearch(nums, 25); 
if (m < 0) {
    m = ~m; 
}

如果二分返回的结果小于 0，就将其取非。这是为啥呢？于是我就对此进行了探索：

🔍 一、binarySearch 为什么会返回负数？

在 Java 中，Arrays.binarySearch() 的设计非常巧妙：

• 如果找到了目标值：返回其 索引（>= 0）
• 如果没找到目标值：返回一个 负数，但这个负数不是随便返回的，它编码了“应该插入的位置”信息

✅ 返回值的规则是：

如果未找到目标值，则返回：-(插入位置) - 1

举个例子：

int[] nums = {10, 20, 30};
int pos = Arrays.binarySearch(nums, 25); // 25 不存在

• 25 应该插入在索引 2（即 30 前面）
• 所以返回值是：-(2) - 1 = -3

📌 二、为什么设计成 -(insertion_point) - 1？

因为如果直接返回 -2，就无法区分：

• 插入位置是 2 → -2
• 插入位置是 0 → 0（但 0 已被“找到元素”使用了）

所以通过 -insertion_point - 1：

• 插入位置 0 → -1
• 插入位置 1 → -2
• 插入位置 2 → -3
• …
  这样就不会和“找到元素返回的 >=0”冲突。

🔁 三、如何从负数恢复“插入位置”？

我们有：

return_value = -insertion_point - 1

移项得：

insertion_point = -return_value - 1

但 Java 提供了一个更巧妙的方式：按位取反 ~

💡 因为：~x == -x - 1

所以：

insertion_point = ~return_value

例子：

int m = Arrays.binarySearch(nums, 25); // 返回 -3
if (m < 0) {
    m = ~m; // ~(-3) = -(-3) - 1 = 3 - 1 = 2
}
// 现在 m = 2，正是应该插入的位置

✅ 四、示例代码

import java.util.Arrays;

public class BinarySearchExample {
    public static void main(String[] args) {
        int[] nums = {10, 20, 30};

        int x = 25;
        int m = Arrays.binarySearch(nums, x);

        if (m >= 0) {
            System.out.println("找到了，索引：" + m);
        } else {
            int insertionPoint = ~m; // 等价于 -m - 1
            System.out.println("没找到，应插入位置：" + insertionPoint);
        }
    }
}

输出：

没找到，应插入位置：2

🧠 五、总结

要得到插入位置：

int insertionPoint = ~m; // 推荐写法
// 或者
int insertionPoint = -m - 1;

✅ ~m 是一种简洁、高效的写法，广泛用于 Java 集合框架中（如 Collections.binarySearch）

✅ 结论：返回负数是为了不浪费返回值空间，同时携带插入位置信息，~m 是恢复该位置的最优方式。