What is the best way to binary search an array via another array?

Question

What would be the best way to do a binary search in an array that you can actually access it via indirection?
Meaning I have an Integer[] that stores the indexes of a String[] that represent the sorted version of the String[]
E.g. Integer[] idxes= {5, 4, 0, 3 , 1, 2} which means that the String[5] or String[idxes[0]] is the lowest string lexicographically.
I hope the description is clear.
What would be the best way to do a binary search via the idexes for a String if it is part of the String[] words ?

What I did is the following:

int pos = Arrays.binarySearch(idexes, -1, new Comparator<Integer>(){

    @Override
    public int compare(Integer o1, Integer o2) {

    if(o1 == -1){
        return k.compareTo(words[o2]);
    }
    else{
        return words[o1].compareTo(k);
      }         
    }
});

where k is the search word and words[] is the String[] I mentioned earlier.
This works, but I don't like the -1 I pass in the binarySearch api.
Is there a better way to approach this?

Not technically an answer but encapsulating the String array and the index array into its own class can at least help hide this implementation detail from the rest of the application. I also don't think it's THAT bad, it doesn't look nice but it's relatively simple, especially with some added comments explaining the rationale. — biziclop
– biziclop, Commented Jul 2, 2012 at 15:13
Having said that, if you search the same array often, you're better off creating a sorted copy. — biziclop
– biziclop, Commented Jul 2, 2012 at 15:19

Louis Wasserman · Accepted Answer · 2012-07-02 15:19:14Z

2

class SortedListView extends AbstractList<String> implements RandomAccess {
  // stringArray, idxes should be fields, initialized in a constructor
  public int size() {
    return stringArray.length;
  }
  public String get(int index) {
    return stringArray[idxes[index]];
  }
};

Then you can use Collections.binarySearch on that List.

answered Jul 2, 2012 at 15:19

Louis Wasserman

200k26 gold badges367 silver badges437 bronze badges

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

2 Comments

Cratylus Over a year ago

+1!One question.Why extends AbstractList and not implements List<String>?

Louis Wasserman Over a year ago

If you just implement List<String>, then you need to implement every single List method individually -- there are at least a dozen different methods. AbstractList fills in that skeleton for you. Initially I thought an anonymous class would suffice, but for Collections.binarySearch you really need to implement RandomAccess for best results, so you need an actual named class.

Collectives™ on Stack Overflow

What is the best way to binary search an array via another array?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related