Collections.binarySearch如何工作？

Question

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

public static void main(String args[]) {
      // create arraylist       
      ArrayList<String>  arlst=new ArrayList<String> ();


      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)在进行此调用之前,必须根据指定的比较器(如方法)将列表按升序排序.

如果数据确实已排序,则该方法将返回所搜索元素的索引(如果已找到),否则(-(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)。插入点定义为将键插入到列表中的点：大于 key 的第一个元素的索引，如果列表中的所有元素都小于指定的键，则为list.size() 。请注意，这保证了当且仅当找到键时返回值>= 0。

所以为了让答案更清楚：-1 = -0 - 1

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