Collections.binarySearch如何工作？

我试图了解Collections.binarySearch如何在Java中工作。 我不太明白我得到的输出。

public static void main(String args[]) { // create arraylist ArrayList arlst=new ArrayList (); arlst.add("A"); arlst.add("D"); arlst.add("C"); arlst.add("B"); arlst.add("E"); int index=Collections.binarySearch(arlst, "D", Collections.reverseOrder()); System.out.println(index); } } 

此代码的输出为-1。

并且当按此顺序插入元素时

  arlst.add("D"); arlst.add("E"); arlst.add("C"); arlst.add("B"); arlst.add("A"); 

结果我得到0。 如果找不到元素，我认为负数是一个结果。 有人可以澄清我收到的输出吗？

Answer 1

您的数据必须根据给定的比较器进行排序，以便二进制搜索按预期工作。 （如果不是，则行为未定义。）

在进行此调用之前，必须根据指定的比较器（通过sort(List, Comparator)方法）将列表按升序sort(List, Comparator) 。

如果数据确实已排序，则该方法将返回所搜索元素的索引（如果已找到），否则(-(insertion point) - 1) ，如文档中所指定。

例：

 // Make sure it's sorted Collections.sort(arlst, Collections.reverseOrder()); int index=Collections.binarySearch(arlst, "D", Collections.reverseOrder()); System.out.println(index); // prints 1 

Answer 2

只是为了让它更清楚 – 为什么输出为-1 。 是的，你没有先排序它是一个很大的错误。 但这里还有其他一些事情需要明确。

正如@aioobe在他的回答中所提到的那样，但我认为他并没有说清楚。 (-(insertion point) - 1)是什么意思？ 这是文档所说的。

搜索关键字的索引，如果它包含在列表中; 否则， （ – （插入点） – 1） 。 插入点定义为键将插入列表的点： 第一个元素的索引大于键 ，或者list.size（），如果列表中的所有元素都小于指定的键。 请注意，当且仅当找到密钥时，这才能保证返回值> = 0。

所以要使答案更清楚： -1 = -0 - 1

我想在这里强调的是输出可能是-2或-3或其他什么。 因为如果列表中的所有元素都小于指定的键 ，则输出将为-list.size() - 1 。