java - Arrays.binarySearch() 如何在不排序的情况下工作

Question

我很想知道当我使用 Arrays.binarySearch 而不进行排序时得到的答案背后的逻辑是什么。

int d[]={6,-4,12,0,-10};
int x=12;
int y=Arrays.binarySearch(d,x);

   System.out.println(y);

输出：2

我正在准备一场Java竞赛，其中会出现这种罕见的情况，所以我问了这个问题。请提供任何可能的解决方案。

Answer 1

你好幸运啊。Java 实现要求对数组进行排序以保证正确答案：

在进行此调用之前，必须对数组进行排序（如通过 sort(int[]) 方法）。如果未排序，则结果未定义。

资源

Answer 2

根据 Java API 参考，if it is not sorted, the results are undefined.

就您而言，您很幸运：二进制搜索是“分而治之”。
该算法着眼于数组的中间。如果它是数字，它会返回（在您的示例中就是这种情况 - 这就是它起作用的原因）。
如果元素大于您搜索的元素，请重复左侧部分（数字较低的部分）。否则使用正确的。
重复直到找到元素。如果您只剩下 1 个元素，并且它不是您搜索的元素，则该元素不在该数组中。在 Java 实现的情况下，它只返回找到的最后一个元素的索引（恰好是i(-(insertion point) - 1)）

Answer 3

你可以得到任何东西。阅读Arrays.binarySearch的 javadocs

在进行此调用之前，必须对数组进行排序（如通过 sort(int[]) 方法）。如果未排序，则结果未定义。

Answer 4

现在javadocs声明

在进行此调用之前，必须对数组进行排序（如通过 sort(int[]) 方法）。如果未排序，则结果为 undefined。如果数组包含多个具有指定值的元素，则无法保证会找到哪一个。