在对象中实现二进制搜索 [英] 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);

User getUserById（ArrayList users，int userid）如何返回具有指定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?

推荐答案

对象排序文章有一个例子来编写自己的 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屋！