Java 在对象中实现二分查找

Implement binary search in objects

提问by Baversjo

Is there any way to implement binary search in a ArrayList with objects? In this example the ArrayList will be sorted with the field 'id'.

有没有办法在带有对象的 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);

How would the "User getUserById( ArrayList users, int userid )" look like if I it should return the user with a specified id using binary search? Is this even possible?

如果我应该使用二进制搜索返回具有指定 id 的用户，“User getUserById(ArrayList users, int userid)”会是什么样子？这甚至可能吗？

采纳答案by coobird

The Object Orderingarticle of The Java Tutorials has an example of writing your own Comparatorin order to perform comparisons on custom types.

The Java Tutorials的Object Ordering文章有一个示例，该示例编写您自己的示例，Comparator以便对自定义类型执行比较。

Then, the ArrayList(or any other List), the key to find, along with Comparatorcan be passed into the Collections.binarySearchmethod.

然后，可以将要查找的键ArrayList（或任何其他List）和 一起Comparator传递到Collections.binarySearch方法中。

Here's an example:

下面是一个例子：

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

回答by Tom Hawtin - tackline

Use Collections.binarySearchwith a Comparator.

使用Collections.binarySearch了Comparator。

回答by grepsedawk

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

回答by Sudipta Deb

You should use binarySearch method only on the sorted ArrayList. so First sort the ArraList and use the same comparator reference (which you used to do the sort) to perform the binarySearch operation.

您应该只对已排序的 ArrayList 使用 binarySearch 方法。所以首先对ArraList 进行排序并使用相同的比较器引用（您用来进行排序的）来执行binarySearch 操作。

回答by rpw

You could also put the comparator in the User class:

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

Then you would do the following to an ArrayList called users:

然后，您将对名为 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");