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

我创建了一个列表，其中保存了一些字符串。但是当我在做的时候二分查找在此列表中，它正在返回负值而该项目是在列表中.

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

Code:

@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()));
    }

}

Output:

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

Reason

您收到奇怪的值，因为您List is 未排序在调用该方法之前，但这是一个要求。因此看看方法文档 https://docs.oracle.com/javase/9/docs/api/java/util/Collections.html#binarySearch-java.util.List-T-:

使用二分搜索算法在指定列表中搜索指定对象。列表必须按升序排列根据其元素的自然顺序（如通过 sort(List) 方法）prior拨打此电话。如果是未排序，结果是不明确的。如果列表包含多个等于指定对象的元素，则无法保证会找到哪一个。

解释

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

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

如果元素之前没有排序，算法很可能会遍历到方向错误显然没有找到该元素。

Solution

解决方案很明显，排序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));
}