Java中的Collections.binarySearch() [英] Collections.binarySearch() in Java

问题描述

我正在使用binarySearch()方法在列表中查找元素的位置.而且我不明白为什么索引是-6.我看到该元素在降序排列后位于位置1.有人可以告诉我为什么我看到-6位吗?谢谢！

I'm using the binarySearch() method to find the position of an element in the list. And I don't understand why the index is -6. I see that the element is at the position 1 after sorting in descending order. Can somebody tell me why I see the position -6? Thank you!

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]

The output is: [100, 50, 30, 10, 2]

位于索引-6

推荐答案

该列表必须按自然升序排列，否则结果将不可预测.

The list must be ordered into ascending natural order otherwise the results are unpredictable.

来自 Javadoc

使用二进制文件在指定列表中搜索指定对象 搜索算法. 列表必须按升序排序 根据其元素的自然顺序(例如 在进行此调用之前，请先执行sort(java.util.List)方法).如果不是 排序后，结果是不确定的.如果列表包含多个 等于指定对象的元素，无法保证 将找到一个.

Searches the specified list for the specified object using the binary search algorithm. The list must be sorted into ascending order according to the natural ordering of its elements (as by the sort(java.util.List) method) prior to making this call. If it is not sorted, the results are undefined. If the list contains multiple elements equal to the specified object, there is no guarantee which one will be found.

---

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

---

Now, if you really want to know why the result is -6, you have to know how the method works internally. It takes the mid index and checks wether it's greater or smaller than the value you're searching for.

如果值更大(在这里是这种情况)，它将占用下半部分并进行相同的计算(低值变为中间值，最大值保持最大值).

If it's greater (which is the case here), it takes the second half and does the same computation (low becomes middle, and max stays max).

最后，如果找不到该键，则该方法返回-(low + 1)，在您的情况下为-(5 + 1)，因为在没有进一步拆分的方法时max索引会变低.

At the end, if the key is not found, the method returns -(low + 1) which in your case is -(5 + 1) because the max index becomes the low when there is no way to split it further.

这篇关于Java中的Collections.binarySearch()的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！