在对象中实现二分查找

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

如果我想使用二分查找方式，编写一个方法"User getUserById(ArrayList users, int userid)"以返回具有指定id的用户，该方法应该如何编写？这是否可行？

- Baversjo

---

使用 Collections.binarySearch - 参见示例用法。 - drorw

Answer 1

《Java教程》中的对象排序文章中提供了编写自己的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);
  }
}

- coobird

---

在诸如“User”之类的对象中允许存储空值非常不好的实践。任何良好而安全的实现将抛出NPE，使得该技术在特定情况下不可行（但在一般情况下是可行的）。 - Mark Jeronimus

Answer 2

您也可以将比较器放在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;
}

如果你想对名为users的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");

- rpw

---

在像“用户”这样的对象中允许存储空值是非常糟糕的实践。任何良好且安全的实现都会抛出NPE，使得在此特定情况下使用该技术不可行（但在一般情况下是可行的）。 - Mark Jeronimus

Answer 3

使用Collections.binarySearch和Comparator。

- Tom Hawtin - tackline

Answer 4

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

- grepsedawk

---

由于两个原因，按照原有代码的方式无法实现：1）用户没有实现可比较接口且没有提供比较器。2）你必须向binarySearch方法传递存储在列表中的实际对象类型，但你传递了一个整数。 - Michael Myers

Answer 5

你应该只在已排序的ArrayList上使用binarySearch方法。因此，首先对ArraList进行排序，并使用相同的比较器引用（用于排序）执行binarySearch操作。

- Sudipta Deb