为什么Collections.binarySearch给出错误的结果? [英] Why is Collections.binarySearch giving wrong results?

问题描述

我创建了一个列表，其中保存了一些字符串.但是，当我在此列表中执行 binary search (二进制搜索)时，它会返回负值，而该项目位于列表中的 .

I have created a List where I have kept some strings. But when I am doing binary search within this list, it is returning negative values while the item is in the list.

到目前为止，当列表中的项目 时，将返回我的知识正值.但是对于某些项目，它返回负值，而对于某些项目，它返回正值.

So far my knowledge positive value will be returned when item in the list. But for some items it is returning negative and for some items positive.

代码:

@Test
public void hello()
{
//  List<String> arlst = new ArrayList<String>();
    List arlst = new ArrayList();
    arlst.add("TP");
    arlst.add("PROVIDES");
    arlst.add("QUALITY");
    arlst.add("TUTORIALS");
    arlst.add("Stop");
    arlst.add("StopP");
    for (Iterator<String> iterator = (Iterator<String>) arlst.iterator();
            iterator.hasNext();)
    {
        Object next = iterator.next();
        System.out.println("next : " + next + " >> Search result : "
            + Collections.binarySearch(arlst, next.toString()));
    }

}

输出:

next : TP >> Search result : -7
next : PROVIDES >> Search result : -1
next : QUALITY >> Search result : 2
next : TUTORIALS >> Search result : -7
next : Stop >> Search result : 4
next : StopP >> Search result : 5

推荐答案

原因

您会收到奇怪的值，因为在调用该方法之前，List未未排序，但这是一项要求.因此，请看看文档:

Reason

You receive strange values since your List is not sorted prior to calling the method, but this is a requirement. Therefore take a look at the methods documentation:

使用二进制搜索算法在指定列表中搜索指定对象.列表必须根据其元素的自然顺序(例如sort(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(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.

---

说明

为了理解该要求，您需要了解二进制搜索的工作方式.这是一个小插图:

---

Explanation

In order to understand that requirement you need to understand how binary search works. Here is a small illustration:

该算法查看中间的元素，并将其与要搜索的元素进行比较.如果给定的针小于中间元素，它将继续向左搜索，否则向右搜索.现在，将查看缩小范围的中间位置的元素，并重复此过程，直到找到该元素或无法再划分范围.

The algorithm takes a look at the element in the middle and compares it to the element to search for. If the given needle is less than the middle element it will continue search to the left, else to the right. It will now take a look at the element to the middle of the reduced range and repeat this process until the element was found or the range can't be divided anymore.

如果元素没有事先排序，则算法很可能会遍历错误的方向，并且显然找不到元素.

If the elements are not sorted prior, the algorithm will very likely traverse to the wrong direction and obviously not find the element.

解决方案很明显，对List进行排序:

The solution is obvious, sort the List:

Collections.sort(arlst);

请注意，您应该不要使用原始类型.因此，写List<String>而不是仅写List.然后，您的类型转换也将变得过时.

Please note that you should not use raw-types. Therefore, write List<String> instead of just List. Then your type-casts will become obsolete too.

完成后，代码可能看起来像

In complete the code might then look like

// Setup list
List<String> list = new ArrayList<>();
list.add("TP");
list.add("PROVIDES");
list.add("QUALITY");
list.add("TUTORIALS");
list.add("Stop");
list.add("StopP");

// Sort list
Collections.sort(list);

// Iterate all elements and use binary search
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
    String element = iter.next();
    System.out.println("element : " + element
        + " >> Search result : "
        + Collections.binarySearch(list, element));
}

这篇关于为什么Collections.binarySearch给出错误的结果?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！