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 index 会变低.

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屋！