Java集合binarySearch不能正常工作

我只是试图使用本机Java binarySearch希望它总能找到第一个出现。但它并不总是返回第一次出现，我在这里做错了什么？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不不gaurante的！谁能给我如何找到一个给定元素第一次发生，去年发生的工作示例（比如用户（10，NULL）？

非常感谢。

来源

2013-03-25 Gob00st

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-25 01:23:31 dasblinkenlight

这是工作，但有没有更好的方式来做到这一点在Java中。在C++中，std :: equal_range，lower_bound，upper_bound很好地完成了这项工作...... – Gob00st 2013-03-25 01:40:31

@ Gob00st我会用类似于STL中的静态方法来包装它。 – dasblinkenlight 2013-03-25 01:46:32

，但你有ID超过1元10你的列表中，这样的binarySearch 是没有错的

的Java手册的binarySearch这样说：。

搜索使用二进制搜索算法指定对象指定列表的列表必须按升序排列。根据元素的自然排序（如b排序（List）方法）。如果没有排序，结果是不确定的。 如果列表包含与指定对象相同的多个元素，则不能保证会找到哪个元素。

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

来源

2013-03-25 01:19:33 gerrytan

从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-25 01:21:02 arcy

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

考虑一个更强大的compareTo实现，它不仅仅根据ID排序，如果项目将具有ID。

来源

2013-03-25 01:21:18

Java集合binarySearch不能正常工作

回答

相关问题