java - 带有 key 提取器的二进制搜索 Java 列表

Question

假设我有:

class Item {
   int id;
   int type;
}

我能做到:

List<Item> items;
Item itemToFind;
Comparator<Item> itemComparator;
Collections.binarySearch(items, itemToFind, itemComparator);

但是，假设我只得到对象的一个​​属性，而不是整个对象，比如说 type对于上面的例子。假设列表按该属性排序，Java 中是否有标准方法或某些已建立的库来执行此操作:

List<Item> items;
Function<Item, Integer> typeExtractor = Item::getType;
int typeToFind;
Comparator<Integer> typeComparator = Integer::compare;
binarySearch(items, typeExtractor, typeToFind, typeComparator);

没有额外的开销(例如，将 List<Item> 转换为 List<Integer> 以调用 Collections.binarySearch 或类似的)？

Answer 1

你的问题是在 Collection<T> java 的二进制搜索实现只允许搜索 T 类型的项目.为了搜索属于 T 的另一种类型，您可以执行以下操作:

1. 将另一种类型包裹在T内，在你的情况下应该是这样的:

List<Item> items;
int typeToFind;

Item itemToFind = new Item(/* random value for id */ 0, typeToFind);
int index = binarySearch(items, itemToFind , (a, b) -> a.getType() - b.getType());

要在此处添加的一些重要说明:

- 项目的比较应该只依赖于“类型”，否则你可能会遇到一些讨厌的错误；

- 项目列表应该排序。排序应该只依赖于`type`(基本上使用与以前相同的比较器)

1. 从初始列表创建一个新列表:

List<Items> items;
int typeToFind

int index = binarySearch(items.stream.map(item -> item.getType()).collect(Collectors.toList()), itemToFind);

据我所知，Java 的标准库不提供带有比较器的二进制搜索实现来实现键相等。如果这些选项不能满足您的要求，您可能应该搜索图书馆或实现您自己的搜索。