オブジェクトでバイナリ検索を実装する

Question

オブジェクトを持つArrayListにバイナリ検索を実装する方法はありますか？この例では、ArrayListはフィールド '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); 

方法「ユーザーgetUserById（ArrayListのユーザーは、int型のユーザーID）は、」私はそれがバイナリ検索を使用して指定されたIDを持つユーザーを返す必要がある場合のように見えるのでしょうか？これも可能ですか？

Answer 1

Object Ordering記事では、カスタムタイプに比較を実行するためにComparatorあなた自身の書き込みの例があります。

そして、ArrayList（または任意の他のList）は、検索するキーは、Comparatorと共にCollections.binarySearchメソッドに渡すことができます。

はここに例を示します

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

Collections.binarySearchにComparatorを使用してください。 Javaのチュートリアルの

Answer 3

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

Answer 4

あなただけのソートのArrayListにbinarySearchメソッドを使用する必要があります。まず、ArraListをソートし、binarySearch操作を実行するのに使ったのと同じコンパレータ参照を使います。あなたはまた、Userクラスにコンパレータを置くことができ

Answer 5

：

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

次にあなたが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");