为什么 Collections.binarySearch 给出了错误的结果？

Question

我创建了一个列表，其中保存了一些字符串。但是当我在这个列表中进行二进制搜索时，它返回负值而该项目在列表中.

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

代码：

@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

Answer 1

必须对列表进行排序才能对其使用 binarySearch。

Answer 2

在API规范中：

使用二进制搜索算法在指定列表中搜索指定对象。在进行此调用之前，必须根据其元素的自然顺序（如通过 sort(List) 方法）对列表进行升序排序。 如果不排序，则结果未定义。如果列表包含多个等于指定对象的元素，则无法保证找到哪一个

Answer 3

原因

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

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.

说明

为了理解该要求，您需要了解二进制搜索的工作原理。这是一个小插图：

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

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

解决方案

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

Collections.sort(arlst);

请注意，您不应不使用原始类型。因此，写 List<String> 而不是 List。那么你的类型转换也会过时。

完整的代码可能看起来像

// 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 给出了错误的结果？

Why is Collections.binarySearch giving wrong results?

java

collections

binary-search

原因

说明

解决方案