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

使用二进制搜索算法在指定的列表中搜索指定的对象。列表必须按照其元素的自然排序(如排序(java.util.List)方法)按升序排序，然后才进行此调用。如果未对其排序，则结果为未定义的。如果列表包含与指定对象相等的多个元素，则无法保证找到哪个元素。

现在，如果你真的想知道结果是-6，你必须知道这个方法在内部是如何工作的。它采用中间索引，并检查它是否大于或小于您正在搜索的值。

如果它更大(这就是这里的情况)，它需要下半部分，并进行相同的计算(低到中间，最大保持最大值)。

最后，如果找不到密钥，则该方法返回-(low + 1)，在您的示例中是-(5 + 1)，因为当无法进一步拆分时，最大索引会变得很低。

Answer 2

您必须按升序排序(根据Collections.binarySearch的文档)，或者将自定义比较器作为第三个参数传递。

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

如果不这样做，将导致未定义结果。

Answer 3

除了需要对列表进行排序外，二进制搜索

如果搜索键包含在列表中，则返回搜索键的索引；否则为(-(插入点)- 1)

(Javadoc)

Ie:负索引是指当被搜索的项目存在时，该索引的负数，减去1。

也就是说。

-1表示它将放在索引0。

-6表示它将放在指数5。