Java集合binarySearch无法正常工作

Question

我只是想尝试使用原生Java二进制搜索,希望它总能找到第一次出现.但它并不总是第一次出现,我在这里做错了什么？

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不是没有gaurante那!任何人都可以举例说明如何找到给定元素的第一次出现和最后一次出现(比如User(10,null)？

非常感谢.

Answer 1

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).

Answer 2

但是您的列表上有1个ID为10的元素。所以binarySearch 没错

Java二进制查询手册说：

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

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