Java集合binarySearch无法正常工作

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

import java.util.*; class BinarySearchWithComparator { public static void main(String[] args) { // Please scroll down to see 'User' class implementation. List l = new ArrayList(); 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 c = new Comparator() { 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 没错

binarySearch的Java手册说：

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

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

Answer 3

来自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. 

Answer 4

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

考虑一个更强大的compareTo实现，如果项目具有ID，则不仅仅通过ID进行排序。