How to binary-search on one field of a List's elements

Question

Let C be a class defined (partially) by

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;
    }
}

and let cs be a List<C> implementing RandomAccess, and sorted on C.getX().

What would be the standard approach to performing a binary search in cs for x1 on C.getX()? (In other words, pretending that each element c is replaced by c.getX() and then we search for x1 among those integers.)

---

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

has the drawback that it requires construction of a new C (which may require lots of dummy arguments and knowledge about C).

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

has the drawback that it creates an entire new list and is presumably O(n).

---

Is there a way to search in the stream directly, without collecting it? Or perhaps some other way to search the original list without having to construct a dummy item?

---

In the absence of a better approach, I would do this:

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();
    }    
}

and then

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

Answer 1

Since you are in control of the Comparator implementation, you can implement a symmetric comparison function that allows to compare instances of C with values of the desired property, i.e. int values (wrapped as an Integer) in case of your x property. It helps to know the factory methods comparing… in the Comparator interface which save you from repeating the code for both sides of the comparison:

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

That way you can search for the int value x1 without wrapping it in a C instance.

Answer 2

Another approach might be this:

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()));

Or, if you don't mind a dependency, you can do this with Guava:

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