Arrays.binarySearch()返回错误索引值问题排查

问题代码 #

int[] nums = {2, 2, 4, 5, 8, 6, 2, 3, 5, 5, 5, 9, 0, 9, 6};
Arrays.sort(nums);
System.out.println(Arrays.toString(nums));  // 输出排序后的数组
System.out.println(Arrays.binarySearch(nums, 6));

排序后数组：[0, 2, 2, 2, 3, 4, 5, 5, 5, 5, 6, 6, 8, 9, 9]

1. 为什么返回11而非第一个6的索引10？ #

Arrays.binarySearch基于二分查找算法实现，该算法的特性是：当数组存在多个匹配目标的元素时，不保证返回第一个匹配项的索引。

二分查找在执行过程中，只要找到一个等于目标值的元素位置，就会直接返回该索引，不会继续向左遍历寻找更早的匹配项。在这个例子中，二分查找的路径刚好命中了索引11的6，因此返回11；当移除一个6后，数组中只剩索引10的6，此时查找自然返回10。

如果需要获取第一个匹配项的索引，不能直接依赖Arrays.binarySearch，需要在找到匹配索引后，手动向左遍历直到找到第一个不等于目标值的位置，再确定第一个匹配项的索引。

2. 关于未找到目标时的返回值 #

教材中“未找到返回-1”的说法不准确，Arrays.binarySearch的官方规则是：

• 找到目标值时：返回任意一个匹配元素的索引（不保证是第一个）
• 未找到目标值时：返回-(插入点) - 1，其中插入点是目标值应该插入数组的位置（插入后仍能保持数组有序）

这种设计的好处是：既可以通过返回值的负号快速判断“未找到”状态，又能通过计算-(返回值 + 1)得到目标值的插入位置，方便后续的数组插入操作。

内容的提问来源于stack exchange，提问作者Skelefish