Request for binary search using functions

[Julian Hyde]

On Dec 9, 2012, at 8:48 PM, Cleber Muramoto <cleber at nightcoders.com.br> wrote:

> Hello, every once in a while I come across the problem of having to use an
> incompatible key to perform a binary search, e.g.:
> 
> int binarySearch(SimpleDateFormat[] array,String pattern){
> ...
> String midVal = array[i].toPattern();
> ...
> }
> 
> (array is sorted using (l,r)->l.toPattern().compareTo(r.toPattern()) )

I think an AbstractList does the trick. It maps values to strings, and only incurs one allocation per search. You need to make it implement RandomAccess so that binarySearch uses an efficient algorithm.

final SimpleDateFormat[] array;
final String seek;
class AbstractRandomAccessList<E> extends AbstractList<E> implements RandomAccess {};

return Collections.binarySearch(
  new AbstractRandomAccessList<String>() {
    public int size() {
      return array.length;
    }
    public String get(int index) {
      return array[index].toPattern();
    },
    seek);

There's also a variant Collections.binarySearch(Object[], int, int) if you wish to search on ranges.

Aside: AbstractList is so useful; it's a shame it is a DAM and not a SAM, and therefore not eligible for lambdafication. Does anyone have any bright ideas how the above could be expressed in lambdas?

Julian