Implémenter la recherche binaire dans les objets

Question

Existe-t-il un moyen d'implémenter la recherche binaire dans une ArrayList avec des objets? Dans cet exemple, ArrayList sera trié avec le champ '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); 

Comment les « utilisateurs (utilisateurs getUserById ArrayList, int userid) » ressembler si je doit renvoyer l'utilisateur avec un identifiant spécifié en utilisant la recherche binaire? Est-ce seulement possible?

Answer 1

L'article Object Ordering de Java Tutoriels a un exemple d'écrire votre propre Comparator afin d'effectuer des comparaisons sur les types personnalisés.

Ensuite, le ArrayList (ou tout autre List), la clé pour trouver, avec Comparator peut être passé dans la méthode Collections.binarySearch.

Voici un exemple:

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); 
    } 
} 

Answer 2

Utilisez Collections.binarySearch avec un Comparator.

Answer 3

import java.util.Collections; 
Collections.binarySearch(users, id); 

Answer 4

Vous devriez utiliser la méthode binarySearch uniquement sur la ArrayList triée. Commencez par trier ArraList et utilisez la même référence de comparaison (que vous avez utilisée pour trier) pour effectuer l'opération binarySearch.

Answer 5

Vous pouvez également mettre le comparateur dans la classe 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; 
} 

Ensuite, vous procédez comme suit à un utilisateur appelé 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");