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)因为在无法进一步拆分时，最大索引变低了。