java - 如何对列表元素的一个字段进行二进制搜索

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值(包装为 Integer )在你的情况下 x属性(property)。它有助于了解工厂方法 comparing… 在 Comparator interface这使您无需为比较的双方重复代码:

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

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