Реализовать двоичный поиск в объектах
-
05-09-2019 - |
Вопрос
Есть ли какой-нибудь способ реализовать двоичный поиск в 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 users, int userid )", если бы я вернул пользователя с указанным идентификатором с помощью двоичного поиска?Возможно ли это вообще?
Решение
В Упорядочение объектов в статье из руководств по 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);
}
}
Другие советы
Вы также могли бы поместить компаратор в пользовательский класс:
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, называемым users:
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 и используйте ту же ссылку на comparator (которую вы использовали для сортировки) для выполнения операции BinarySearch.