Implementare la ricerca binaria negli oggetti

Question

Esiste un modo per implementare la ricerca binaria in un oggetto ArrayList con oggetti? In questo esempio, ArrayList verrà ordinato con il campo '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); 

Come sarebbero i "User getUserById (utenti ArrayList, int id utente)" apparire come se mi deve restituire all'utente un ID specificato usando la ricerca binaria? È possibile?

Answer 1

La Object Ordering articolo di Java Tutorials ha un esempio di scrivere il proprio Comparator al fine di effettuare i confronti sui tipi personalizzati.

Poi, il ArrayList (o qualsiasi altro List), la chiave per trovare, insieme a Comparator può essere passato nel metodo Collections.binarySearch.

Ecco un esempio:

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

Utilizzare Collections.binarySearch con un Comparator.

Answer 3

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

Answer 4

si dovrebbe utilizzare il metodo binarySearch solo sul ArrayList ordinato. quindi Prima ordina l'ArraList e usa lo stesso riferimento di comparatore (che hai usato per fare l'ordinamento) per eseguire l'operazione binarySearch.

Answer 5

Si potrebbe anche mettere il comparatore nella 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; 
} 

allora si dovrebbe effettuare le seguenti operazioni a un ArrayList chiamati utenti:

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