如何二进制搜索List的元素的一个字段

Question

让 C被一个类中定义(部分地)由

private static class C {
    private final int x;
    // lots more fields be here

    public C(int x, /* lots more arguments here */) {
        this.x = x;
        // lots more fields initialized here
    }

    public int getX(){
        return x;
    }
}

让cs是一个List<C>实现RandomAccess,并分类对C.getX().

什么是标准的方法来执行的二进制搜索cs的x1上C.getX()？(换句话说,假装每个元素c都被替换c.getX(),然后我们x1在这些整数中搜索.)

---

Collections.binarySearch(
    cs,
    new C(x1,/* dummy arguments */),
    (a,b) -> Integer.compare(a.getX(),b.getX())
);

它的缺点是它需要构造一个新的C(可能需要大量的伪参数和知识C).

Collections.binarySearch(
    cs.stream().map(C::getX).collect(Collectors.toList()),
    x1
);

它的缺点是它创建了一个完整的新列表,大概是O(n).

---

有没有办法直接搜索流,而不收集它？或者也许还有其他方法可以搜索原始列表而无需构建虚拟项目？

---

如果没有更好的方法,我会这样做:

public class MappedView<T,E> extends AbstractList<E> {

    public static <T,E> MappedView<T,E> of(List<T> backingList, Function<T,E> f){
        return new MappedView<>(backingList, f);
    }

    private final List<T> backingList;
    private final Function<T,E> f;

    private MappedView(List<T> backingList, Function<T,E> f){
        this.f = f;
        this.backingList = backingList;
    }

    @Override
    public E get(int i) {
        return f.apply(backingList.get(i));
    }

    @Override
    public int size() {
        return backingList.size();
    }    
}

然后

Collections.binarySearch(
    MappedView.of(cs, c -> c.getX()),
    x1
);

Answer 1

由于您可以控制实现Comparator，因此您可以实现一个对称比较函数，该函数允许将 的实例C与所需属性的值进行比较，即您的属性的int值（包装为 ）。了解接口中的工厂方法很有帮助，这样您就不必为比较双方重复代码：Integerxcomparing\xe2\x80\xa6Comparator

\n\n

int index = Collections.binarySearch(cs, x1,\n    Comparator.comparingInt(o -> o instanceof C? ((C)o).getX(): (Integer)o));\n

\n\n

这样您就可以搜索该int值x1，而无需将其包装在C实例中。

\n

Answer 2

另一种方法可能是这样的：

private static class C {
    private final int x;
    // lots more fields be here

    private C() {
    }

    public C(int x, /* lots more arguments here */) {
        this.x = x;
        // lots more fields initialized here
    }

    public int getX(){
        return x;
    }

    public static C viewForX(int x) {
        C viewInstance = new C();
        viewInstance.x = x;
        return viewInstance;
    }
}

Collections.binarySearch(cs, 
    C.viewForX(x1), 
    (a,b) -> Integer.compare(a.getX(),b.getX()));

或者，如果您不介意依赖，您可以使用Guava执行此操作：

List<Integer> xs = Lists.transform(cs, C::getX());
Collections.binarySearch(xs, x1);