5

我只是想使用本机 Java binarySearch，希望它总能找到第一次出现的地方。但它并不总是返回第一次出现，我在这里做错了什么？

import java.util.*;

class BinarySearchWithComparator
{
  public static void main(String[] args)
  {
    // Please scroll down to see 'User' class implementation.
    List<User> l = new ArrayList<User>();
    l.add(new User(10, "A"));
    l.add(new User(10, "A"));
    l.add(new User(10, "A"));

    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));


    l.add(new User(30, "C"));
    l.add(new User(30, "C"));
    l.add(new User(30, "C"));
    l.add(new User(30, "C"));

    Comparator<User> c = new Comparator<User>() {
      public int compare(User u1, User u2) {
        return u1.getId().compareTo(u2.getId());
      }
    };

    // Must pass in an object of type 'User' as the key.
    // The key is an 'User' with the 'id' which is been searched for.
    // The 'name' field is not used in the comparison for the binary search,
    // so it can be a dummy value -- here it is omitted with a null.
    //
    // Also note that the List must be sorted before running binarySearch,
    // in this case, the list is already sorted.
    Collections.sort(l,c);

    int index = Collections.binarySearch(l, new User(10, null), c);
    System.out.println(index);

    index = Collections.binarySearch(l, new User(20, null), c);
    System.out.println(index);

    index = Collections.binarySearch(l, new User(30, null), c);
    System.out.println(index);

    index = Collections.binarySearch(l, new User(42, null), c);
    System.out.println(index);
  }
}

class User {
  private int id;
  private String name;

  public User(int id, String name) {
    this.id = id;
    this.name = name;
  }

  public Integer getId() {
    return Integer.valueOf(id);
  }
}

========

Result:
2 //not 0 ?
6 //not 3?
10 //ok
-15  ok

Why first 10 is not index 0 ?
Why first 20 is not index 3 ?
OK , 30 first occurrence is index 10

=======================================

更新

现在看来，API 并不能保证这一点！谁能给我一个工作示例，说明如何找到给定元素的第一次出现和最后一次出现（比如用户（10，null）？

非常感谢。

4

4 回答 4

10

Java 不保证它将返回相等元素中的哪个元素。当您在相等范围内有多个元素时，您需要向下遍历列表以找到与您要查找的内容相等的第一个元素，如下所示：

User lookFor = new User(30, null);
index = Collections.binarySearch(l, lookFor, c);
while (index > 0 && c.compare(lookFor, l[index-1]) == 0) {
    index--;
}
// At this point the index is at the first element of the equal range

您可以将此逻辑包装在静态函数中，以避免每次都编写显式循环。

请注意，如果您的集合是随机访问的，这将导致最坏情况下的性能（当有许多相同的元素时）从 O(lg(n)) 降级到 O(n)。

于 2013-03-25T01:23:31.227 回答
5

但是您的列表中有超过 1 个 id 为 10 的元素。所以 binarySearch没有错

binarySearch 的 Java 手册是这样说的：

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

http://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#binarySearch(java.util.List , T)

于 2013-03-25T01:19:33.027 回答
1

来自 Array.binarySearch() 上的 javadoc：

Searches a range of the specified array of bytes for the specified value using the
binary search algorithm. The range must be sorted (as by the sort(byte[], int, int) 
method) prior to making this call. If it is not sorted, the results are undefined. 
If the range contains multiple elements with the specified value, there is no 
guarantee which one will be found.
于 2013-03-25T01:21:02.110 回答
1

出于排序目的，您列表中的许多项目都是相同的。如果两个项目具有相同的 ID，那么从排序的角度来看，使用哪一个并不重要。Collections.binarySearch 只是将列表分成两半，直到找到匹配项。一旦找到匹配项，它就不会检查前一个项目是否也匹配，它只会返回索引。

考虑一个更健壮的 compareTo 实现，如果项目将具有 ID，它不仅按 ID 排序。

于 2013-03-25T01:21:18.330 回答