Implementar búsqueda binaria en objetos

Question

¿Hay alguna forma de implementar la búsqueda binaria en una ArrayList con objetos? En este ejemplo, ArrayList se ordenará con el 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); 

¿Cómo el "Usuario getUserById (usuarios ArrayList, int id de usuario)" parecerse a si es conveniente devolver al usuario un id especificado mediante la búsqueda binaria? ¿Esto es posible?

Answer 1

El artículo Object Ordering de los tutoriales de Java tiene un ejemplo de escritura de su propia Comparator el fin de realizar comparaciones de tipos personalizados.

Entonces, el ArrayList (o cualquier otra List), la clave para encontrar, junto con Comparator pueden transferirse al método Collections.binarySearch.

He aquí un ejemplo:

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

Usa Collections.binarySearch con un Comparator.

Answer 3

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

Answer 4

Usted debe utilizar el método busquedaBinaria sólo en el ArrayList ordenada. entonces primero clasifique la ArraList y use la misma referencia del comparador (que utilizó para ordenar) para realizar la operación binarySearch.

Answer 5

También puede poner el comparador en la clase de usuario:

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

allí tendría que hacer lo siguiente para un ArrayList llamadas de los usuarios:

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