Binäre Suche in Objekten implementieren

Question

Gibt es eine Möglichkeit, die binäre Suche in einer ArrayList mit Objekten zu implementieren? In diesem Beispiel wird die ArrayList mit dem Feld 'id' sortiert.

class User{ 
public int id; 
public string name; 
} 

ArrayList<User> users = new ArrayList<User>(); 

sortById(users); 

int id = 66 
User searchuser = getUserById(users,id); 

Wie würde die „User getUserById (Arraylist Benutzer, int Benutzer-ID)“ aussehen, wenn ich es soll den Benutzer mit einer bestimmten ID mit binärer Suche zurückkehren? Ist das überhaupt möglich?

Answer 1

Der Object Ordering Artikel der Java-Tutorials hat ein Beispiel für Ihre eigenen Comparator, um das Schreiben Vergleiche auf benutzerdefinierte Typen auszuführen.

Dann wird die ArrayList (oder jede andere List), der Schlüssel zu finden, zusammen mit Comparator in die Collections.binarySearch Methode übergeben werden.

Hier ist ein Beispiel:

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

Verwenden Sie Collections.binarySearch mit einem Comparator.

Answer 3

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

Answer 4

Sie sollten nur binarysearch Methode verwenden, auf der sortierten Arraylist. Also sortiere zuerst die ArraList und benutze die gleiche Vergleichsreferenz (mit der du die Sortierung durchführte), um die binarySearch-Operation durchzuführen.

Answer 5

könnten Sie den Komparator in der User-Klasse setzen auch:

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

Dann rief Benutzer an einem Arraylist folgende Sie tun würden: auf dem Code

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