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

    public int compare(Item a, Item b) 

    { 

        return a.getType() - b.getType(); 

    } 

}

项目，需要公开类型或属性的 getter。如果使用 id 也是一样。

但是，不确定您建议我如何调用 Collections.binarySearch

用法没有改变（改变的是比较器对象内部的比较方式）：

Item itemToFind = new Item();

itemToFind.setType(typeToFind);

Collections.binarySearch(items, itemToFind, comparator );

在对这个问题进行了一些思考之后：

使用 anItem作为 needle 的另一种方法是Comparator基于接口Item和 needle 实现。

返回 int 值的接口：

 public interface Intgettable{

     public int getInt();

 }

Item应该必须实现这个接口：

public class Item implements Intgettable{

     private int id;

     private int type;

     public void setId(int id){ 

         this.id = id;

     }

     public void setType(int type){ 

         this.type = type;

     }

     public int getId(){

         return id;

     }

     public int getType(){

         return type;

     }

     public int getInt(){

         return type;

     }

 }

搜索的关键是Intgettable可以创建的：

1 - 使用扩展的类Intgettable。

public static class MyItemKey implements Intgettable{

     private int value;

     public MyItemKey(int v){

         this.value = v;

     }

     @Override

     public int getInt(){

         return value;

     }

}

MyItemKey typeToFind = new MyItemKey(6);

2 - 作为方法内的匿名类。

Intgettable typeTofind = new Intgettable(){

        private int value = 6;

        public int getInt(){

            return value;

        }

};

3 - 或使用 lambda 版本：

Intgettable typeTofind = ()->{return 6;};

将Comparator是：

Comparator<Intgettable> comparator = new Comparator<Intgettable>(){

        public int compare(Intgettable a, Intgettable b){

            return a.getInt() - b.getInt();

        }

};

最后在二分查找中使用它：

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 typeToFind

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

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