java - 为什么 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

原因

自 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));
}