带有密钥提取器的二进制搜索 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

比较器仍然是Comparator<Item>. 您将更改的是比较器的实现以评估类型而不是 id。Comparator<Item> comparator = new Comparator<Item>(){&nbsp; &nbsp; public int compare(Item a, Item b)&nbsp;&nbsp; &nbsp; {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; return a.getType() - b.getType();&nbsp;&nbsp; &nbsp; }&nbsp;}项目，需要公开类型或属性的 getter。如果使用 id 也是一样。但是，不确定您建议我如何调用 Collections.binarySearch用法没有改变（改变的是比较器对象内部的比较方式）：Item itemToFind = new Item();itemToFind.setType(typeToFind);Collections.binarySearch(items, itemToFind, comparator );在对这个问题进行了一些思考之后：使用 anItem作为 needle 的另一种方法是Comparator基于接口Item和 needle 实现。返回 int 值的接口：&nbsp;public interface Intgettable{&nbsp; &nbsp; &nbsp;public int getInt();&nbsp;}Item应该必须实现这个接口：public class Item implements Intgettable{&nbsp; &nbsp; &nbsp;private int id;&nbsp; &nbsp; &nbsp;private int type;&nbsp; &nbsp; &nbsp;public void setId(int id){&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;this.id = id;&nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp;public void setType(int type){&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;this.type = type;&nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp;public int getId(){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return id;&nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp;public int getType(){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return type;&nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp;public int getInt(){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return type;&nbsp; &nbsp; &nbsp;}&nbsp;}搜索的关键是Intgettable可以创建的：1 - 使用扩展的类Intgettable。public static class MyItemKey implements Intgettable{&nbsp; &nbsp; &nbsp;private int value;&nbsp; &nbsp; &nbsp;public MyItemKey(int v){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;this.value = v;&nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp;@Override&nbsp; &nbsp; &nbsp;public int getInt(){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return value;&nbsp; &nbsp; &nbsp;}}MyItemKey typeToFind = new MyItemKey(6);2 - 作为方法内的匿名类。Intgettable typeTofind = new Intgettable(){&nbsp; &nbsp; &nbsp; &nbsp; private int value = 6;&nbsp; &nbsp; &nbsp; &nbsp; public int getInt(){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return value;&nbsp; &nbsp; &nbsp; &nbsp; }};3 - 或使用 lambda 版本：Intgettable typeTofind = ()->{return 6;};将Comparator是：Comparator<Intgettable> comparator = new Comparator<Intgettable>(){&nbsp; &nbsp; &nbsp; &nbsp; public int compare(Intgettable a, Intgettable b){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return a.getInt() - b.getInt();&nbsp; &nbsp; &nbsp; &nbsp; }};最后在二分查找中使用它：Collections.binarySearch(items, typeToFind, comparator )

Answer 2

您的问题是，在Collection<T>java 的二进制搜索实现中，只允许搜索 type 的项目T。为了搜索属于 的其他类型T，您可以执行以下操作：将另一种类型包装在里面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`，否则你可能会遇到一些讨厌的错误；- 项目列表应该被排序。排序应该仅且仅取决于“类型”（基本上使用与以前相同的比较器）从初始列表创建一个新列表：List<Items> items;int typeToFindint index = binarySearch(items.stream.map(item -> item.getType()).collect(Collectors.toList()), itemToFind);据我所知，Java 的标准库没有提供带有键相等比较器的二进制搜索实现。如果这些选项不能满足您的要求，您可能应该搜索一个库或实现您自己的搜索。