在对象中实现二进制搜索
有没有办法在带有对象的ArrayList中实现二进制搜索？ 在此示例中，ArrayList将使用字段“id”进行排序。
class User{ public int id; public string name; } ArrayList users = new ArrayList(); sortById(users); int id = 66 User searchuser = getUserById(users,id); 如果我应该使用二进制搜索返回具有指定id的用户，那么“User getUserById（ArrayList users，int userid）”如何？ 这有可能吗？
The Java Tutorials的Object Ordering文章有一个编写自己的Comparator的例子，以便对自定义类型进行比较。
然后，可以将ArrayList （或任何其他List ），要查找的键以及Comparator传递到Collections.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(20, "B")); 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. int index = Collections.binarySearch(l, new User(20, null), c); System.out.println(index); // Output: 1 index = Collections.binarySearch(l, new User(10, null), c); System.out.println(index); // Output: 0 index = Collections.binarySearch(l, new User(42, null), c); System.out.println(index); // Output: -4 // See javadoc for meaning of return value. } } 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); } }
您还可以将比较器放在User类中：
public class User implements Comparable, Comparator { public User(int id, String name) { this.id = id; this.name = name; } @Override public int compareTo(User u) { return id - u.getID(); } @Override public int compare(User u1, User u2) { return u1.getID() - u2.getID(); } public int getID() { return id; } public String getName() { return name; } private int id; private String name; }
然后，您将对名为users的ArrayList执行以下操作：
ArrayList users = new ArrayList (); users.add(new User(3, "Fred")); users.add(new User(42, "Joe")); users.add(new User(5, "Mary")); users.add(new User(17, "Alice")); Collections.sort(users); int index = Collections.binarySearch(users, new User(5, null)); if(index >= 0) System.out.println("The user name of id 5 is: "+users.get(index).getName()); else System.out.println("ID 5 is not in the list");
将Collections.binarySearch与Comparator一起使用。
import java.util.Collections; Collections.binarySearch(users, id);
您应该仅对已排序的ArrayList使用binarySearch方法。 首先对ArraList进行排序并使用相同的比较器引用（您用于排序）来执行binarySearch操作。