Java中的Collections.binarySearch()

Question

我正在使用binarySearch()方法来查找列表中元素的位置.我不明白为什么索引是-6.我看到元素在按降序排序后位于位置1.谁能告诉我为什么我看到-6的位置？谢谢!

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Test
{
    public static void main(String[] args)
    {
        List<Integer> al = new ArrayList<>();
        al.add(100);
        al.add(30);
        al.add(10);
        al.add(2);
        al.add(50);

        Collections.sort(al, Collections.reverseOrder()); 
        System.out.println(al);

        int index = Collections.binarySearch(al, 50);

        System.out.println("Found at index " + index);
    }
}

输出为:[100,50,30,10,2]

在索引-6处找到

Answer 1

该列表必须按升序自然顺序排序,否则结果将无法预测.

来自Javadoc

使用二进制搜索算法在指定列表中搜索指定的对象.在进行此调用之前,必须根据元素的自然顺序(通过sort(java.util.List)方法)将列表按升序排序.如果未排序,则结果未定义.如果列表包含多个等于指定对象的元素,则无法保证找到哪个元素.

现在,如果你真的想知道为什么结果为-6,你必须知道该方法如何在内部工作.它需要中间索引并检查它是否大于或小于您正在搜索的值.

如果它更大(这是这里的情况),它需要后半部分并进行相同的计算(低变为中间,最大值保持最大).

最后,如果找不到该键,则该方法返回-(low + 1)的情况是,-(5 + 1)因为当无法进一步拆分时,最大索引变为低.