Binary Search using Comparator

Question

I'm struggling to get this to work. I need to write a functor that will work with a binarySearch algorithm to find a ladder that has a length between 12 and 15 units.

Here's the binary search:

public static <AnyType> int binarySearch(GenericSimpleArrayList<AnyType> a, AnyType x, Comparator<? super AnyType> cmp) {
    int low = 0;
    int high = a.size() - 1;
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (cmp.compare(a.get(mid), x) < 0) {
            low = mid + 1;
        } else if (cmp.compare(a.get(mid), x) > 0) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return NOT_FOUND; // NOT_FOUND = -1
}

and here's what I have for the functor:

public class FindLadder implements Comparator<Ladder>{

  @Override
  public int compare(Ladder lhs, Ladder rhs) {
    return 0;
}

}

Now obviously, the functor won't do anything at the moment, I don't know what to put in the functor in order to determine if a ladder falls between x and x length, nor do I know how to implement the binarySearch method. I would need to pass a Ladder object as x in order for the functor to work, as far as I can tell, but then how do I stipulate the length that I am searching for? The Ladder class has a .length() method.

The array is sorted in the order of shortest to longest. I cannot change the binarySearch code at all. I can only implement a functor that will do what I need.

Answer 1

Short version by hacking Collections.binarySearch

The framework has built-in binary search and generic List<T> interface, you should use them.

The built-in binarySearch function always supplies the pivot element to the comparator as the second argument. This is undocumented behaviour, but we can exploit that, using the following comparator:

public static class FindLadderInterval implements Comparator<Ladder> {
  public final int min, max;
  public FindLadderInterval(int min, int max) {
    this.min = min;
    this.max = max;
  }
  @Override
  public int compare(Ladder lhs, Ladder rhs) {
    // ignore rhs
    int length = lhs.length();
    return length < this.min ? -1 : length > this.max ? 1 : 0;
  }
}

Then you can use it this way:

int index = Collections.binarySearch(list, null, new FindLadderInterval(12, 15));

Working example:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main2 {

  public static class Ladder {
    private final int _length;

    public Ladder(int length) {
      this._length = length;
    }

    public int length() {
      return this._length;
    }

    @Override
    public String toString() {
      return "Ladder(" + this._length + ")";
    }
  }

  public static class FindLadderInterval implements Comparator<Ladder> {
    public final int min, max;

    public FindLadderInterval(int min, int max) {
      this.min = min;
      this.max = max;
    }

    @Override
    public int compare(Ladder lhs, Ladder rhs) {
      // ignore rhs
      int length = lhs.length();
      return length < this.min ? -1 : length > this.max ? 1 : 0;
    }
  }

  public static void main(String[] args) {
    List<Ladder> list = new ArrayList<Ladder>();

    list.add(new Ladder(1));
    list.add(new Ladder(2));
    list.add(new Ladder(6));
    list.add(new Ladder(13));
    list.add(new Ladder(17));
    list.add(new Ladder(21));

    int index = Collections.binarySearch(list, null,
        new FindLadderInterval(12, 15));
    System.out.println("index: " + index);
    System.out.println("ladder: " + list.get(index));
  }
}

Long version using proper algorithms

Your task to find an element in an interval is not a simple binary search, but we can implement it using a binarySearch function similar to the built-in one, because that returns the insertion index as a negative number if the element was not found. So we can search for the element at the end of the interval, if it's found then return it, and if it's not found simply check if the item at the insertion index is in the interval, and return that. This way the algorithm will return the last element in the interval.

public static <T, R extends Comparable<? super R>> int intervalBinarySearchBy(
    List<T> list, R min, R max, Function<? super T, ? extends R> selector) {
  int idx = binarySearchBy(list, max, selector);
  if (idx >= 0) return idx;
  // Collections.binarySearch returns the insertion index binary
  // negated if the element was not found
  idx = ~idx;
  return (idx < list.size()
    && min.compareTo(selector.apply(list.get(idx))) <= 0) ? idx : -1;
}

To use the built-in Collections.binarySearch or your function, you need to provide a representative element, which is pretty hard when for example you order strings by their lengths. To find a string with a length of 15 you must provide a string with length of 15. That's why I like the python style ordering much more, which uses key functions or selectors. Basically, you don't need comparisons but a mapping to a comparable value. For example a mapping from String to Integer like s -> s.length(). This makes possible to implement sweet functions like these (lambdas make it pretty):

List<Person> list = getPersons();
Person youngest = minBy(list, p -> p.getAge());
Person tallest = maxBy(list, p -> p.getHeight());
Person person42 = findBy(list, 42, p -> p.getAge());
sortBy(list, p -> p.getAge());

See, don't need a Comparator to order items by a property. Simple task, simple solution. Unfortunately, I am not aware of functions like this in either the standard library or third-parties. But they can be implemented.

A working example in Java 8:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.function.Function;

public class Main {

  public static class Collections2 {

    /**
     * Mimics Collections.binarySearch
     * 
     * @param list
     * @param pivotKey
     * @param selector
     * @return
     */
    public static <T, R extends Comparable<? super R>> int binarySearchBy(
        List<T> list, R pivotKey,
        Function<? super T, ? extends R> selector) {
      int low = 0;
      int high = list.size() - 1;
      while (low <= high) {
        int mid = (low + high) >>> 1;
        int ord = selector.apply(list.get(mid)).compareTo(pivotKey);
        if (ord < 0) {
          low = mid + 1;
        } else if (ord > 0) {
          high = mid - 1;
        } else {
          return mid;
        }
      }
      return ~high; // bitwise negated insertion point /* -(a+1) == ~a */
    }

    /**
     * Finds the index of the last element in the interval, or returns -1 if
     * no such element was found.
     * 
     * @param list
     * @param min
     * @param max
     * @param selector
     * @return
     */
    public static <T, R extends Comparable<? super R>> int intervalBinarySearchBy(
        List<T> list, R min, R max, Function<? super T, ? extends R> selector) {
      int idx = binarySearchBy(list, max, selector);
      if (idx >= 0) return idx;
      // Collections.binarySearch returns the insertion index binary
      // negated if the element was not found
      idx = ~idx;
      return (idx < list.size()
        && min.compareTo(selector.apply(list.get(idx))) <= 0) ? idx : -1;
    }

    public static <T, R extends Comparable<? super R> > Comparator<T> comparatorBy(
        Function<? super T, ? extends R> selector) {
      return (a, b) -> selector.apply(a).compareTo(selector.apply(b));
    }
  }

  public static Function<Ladder, Integer> LENGTH_OF = a -> a.length();

  public static class Ladder {
    private final int _length;

    public Ladder(int length) {
      this._length = length;
    }

    public int length() {
      return this._length;
    }

    @Override
    public String toString() {
      return "Ladder(" + this._length + ")";
    }
  }

  public static void main(String[] args) {
    List<Ladder> list = new ArrayList<Ladder>();
    list.add(new Ladder(5));
    list.add(new Ladder(9));
    list.add(new Ladder(14));
    list.add(new Ladder(7));
    list.add(new Ladder(22));
    list.add(new Ladder(23));
    list.add(new Ladder(11));
    list.add(new Ladder(9));

    Collections.sort(list, Collections2.comparatorBy(LENGTH_OF));

    int i = 0;
    for (Ladder s : list) {
      System.out.println("" + (i++) + ": " + s);
    }

    int foundIdx = Collections2.intervalBinarySearchBy(list, 12, 15,
        LENGTH_OF);
    System.out.println("Index: " + foundIdx);
    System.out.println(list.get(foundIdx));
  }
}