在对象中实现二分查找 [英] Implement binary search in objects

问题描述

有没有办法在带有对象的 ArrayList 中实现二分查找?在此示例中，ArrayList 将使用字段id"进行排序.

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'.

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

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

sortById(users);

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

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

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?

推荐答案

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

The Object Ordering article of The Java Tutorials has an example of writing your own Comparator in order to perform comparisons on custom types.

然后，ArrayList(或任何其他List)，要查找的键，以及Comparator 可以传递到Collections.binarySearch 方法.

Then, the ArrayList (or any other List), the key to find, along with Comparator can be passed into the Collections.binarySearch method.

这是一个例子:

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

这篇关于在对象中实现二分查找的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！