Implementierung der binären Suche in Objekten

Question

Gibt es eine Möglichkeit, binäre Suche in einer ArrayList mit Objekten zu implementieren? In diesem Beispiel wird die ArrayList nach 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 Funktion "User getUserById( ArrayList users, int userid )" aussehen, wenn sie den Benutzer mit einer bestimmten ID mittels binärer Suche zurückgeben soll? Ist dies überhaupt möglich?

Answer 1

En Objektbestellung Artikel von The Java Tutorials enthält ein Beispiel für das Schreiben einer eigenen Comparator um Vergleiche mit benutzerdefinierten Typen durchzuführen.

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

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

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

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 würden Sie das Folgende mit einer ArrayList namens users machen:

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

Answer 3

使用方法 Collections.binarySearch mit einer Comparator .

Answer 4

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

Answer 5

Sie sollten die binarySearch-Methode nur auf die sortierte ArrayList anwenden. Sortieren Sie also zunächst die ArraList und verwenden Sie denselben Komparatorbezug (den Sie für die Sortierung verwendet haben), um die binarySearch-Operation durchzuführen.