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不能正常工作

回答

相關問題