Implement binary search using the `Collections.binarySearch` signature

Question

Here is my attempt at implementing the binary search that must follow:

static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

However, I would like to avoid code duplication and delegate one of the implementations to the other (currently, the first to the second). To do that I need to get rid of the wildcard ? and use a second generic type like so:

public class BinarySearch {
    public static <Q extends Comparable<? super T>, T>
    int search(List<Q> xs, T x) {
        return search(xs, x, Q::compareTo);
    }

    public static <T>
    int search(List<? extends T> xs, T x, Comparator<? super T> cmp) {
        int l = 0, r = xs.size() - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;

            if (cmp.compare(xs.get(mid), x) == 0)
                return mid;

            if (cmp.compare(xs.get(mid), x) < 0)
                r = mid - 1;
            else
                l = mid + 1;
        }

        return xs.size();
    }
}

Unfortunately, this does not compile, failing with the error:

Non-static method cannot be referenced from a static context

How could I fix that?

PS: if you wonder why the signatures from Collections look the way they do, here is an explanation: How do these two generic signatures for Collections.binarySearch differ?

PPS: there used to be (a now deleted) answer that you cannot pass T::compareTo in place where a Comparator is expected. Well, I believe that you can, here is my working implementation of QuickSort that does exactly that: https://github.com/all3fox/algos-java/blob/481f2c71952bf2c7510cb93cc1af8e90016ccf3b/src/main/java/io/github/all3fox/sort/QuickSort.java

Your binary search has more issue. It's missing a return statement in case the element is not found. — Codo
– Codo, Commented Oct 22, 2016 at 19:19

Bernd Ebertz · Accepted Answer · 2016-10-22 20:57:21Z

2

Actually I don't understand why use Q:

public static <T extends Comparable<T>>
int search(List<? extends T> xs, T x) {
    return search(xs, x, T::compareTo);
}

will compile and looks sufficient to me. It allows me to do both:

BinarySearch.search(new ArrayList<Timestamp>(), new Date());
BinarySearch.search(new ArrayList<Date>(), new Timestamp(0L));

A very important point here is that this actually means (more or less):

int search(List<? extends T> xs, final T x) {
    return search(xs, x, new Comparator<T>() {
      @Override
      public int compare(T o1, T o2) {
        return x.compareTo(o2);
      }
    });
}

Now we clearly can see: x needs to be of type Comparable. This wasn't stated in your approach. Instead there was a type Q defined, but no participant actually was of this type. So the Comparator wasn't strictly compatible, but it has to, as the compareTo-method of x is the implementation of the comparator. BTW another approach is to use Comparator.naturalOrder() for the trick, but still T must be defined to be a Comparable.

edited Oct 22, 2016 at 20:57

answered Oct 22, 2016 at 19:37

Bernd Ebertz

1,3278 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

alisianoi Over a year ago

I have updated my question with the link to my previous quesion as to "why default signatures are so complicated", here it is stackoverflow.com/questions/40195450/…

Bernd Ebertz Over a year ago

@all3fox ok, I did an edit. But still no Q... Actually I didn't see the Q in the question you mentioned.

alisianoi Over a year ago

you have moved the extends Comparable<T> bound out of the parameter list before the return value. Could you please explain what difference it makes? (or point to a doc). Is that just a shorthand so as not to write extends Comparable<T> in two places in the parameter list?

Collectives™ on Stack Overflow

Implement binary search using the `Collections.binarySearch` signature

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related