Есть ли способ реализовать двоичный поиск в ArrayList с объектами? В этом примере ArrayList будет сортироваться с полем "id".
class User{
public int id;
public string name;
}
ArrayList<User> users = new ArrayList<User>();
sortById(users);
int id = 66
User searchuser = getUserById(users,id);
Как будет выглядеть "User getUserById (пользователи ArrayList, int userid)", если я должен вернуть пользователя с указанным идентификатором, используя двоичный поиск? Возможно ли это?
Object Ordering в статье "Учебники Java" есть пример написания собственного 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<User> l = new ArrayList<User>();
l.add(new User(10, "A"));
l.add(new User(20, "B"));
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.
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<User>, Comparator<User>
{
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;
}
Затем вы должны сделать следующее для пользователей ArrayList:
ArrayList<User> users = new ArrayList<User>();
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);
Вы должны использовать метод binarySearch только для отсортированного ArrayList. поэтому сначала соберите ArraList и используйте ту же самую ссылку сравнения (которую вы использовали для сортировки) для выполнения операции binarySearch.