using multiple comparators in a java binarySearch

Question

How do I use multiple comparators in a binarySearch in java... I'm trying to sort a list of contestants which are sorted by name and their starting number.

The problem is if two contestants have the same name I get an IndexOutOfBoundsException so I want to do a secondary binarySearch using the starting number (which is unique) but still keeping them in the right order with names.

This is what I've got right now:

static void add(Contestant c){
    int pos = Collections.binarySearch(byName, c, new ConNameCmp());
    if (pos >= 0){
        pos = Collections.binarySearch(byName, c, new ConStartCmp());
    }
    byName.add(-pos-1, c);

Is there any specific reason for your avoiding of TreeSet? — biziclop
– biziclop, Commented Mar 2, 2011 at 15:32

Sean Patrick Floyd · Accepted Answer · 2011-03-02 16:20:09Z

5

One Comparator only

Don't use two Comparators, use a single Comparator that compares both values:

public int compare(Foo a, Foo b){
    // compare bar() values first
    int result = a.bar().compareTo(b.bar());
    // compare baz() values only if bar() values are different
    if(result==0){
        result = a.baz().compareTo(b.baz());
    }
    return result;
}

(In your case bar() is the name and baz() is the number).

Use Libraries

Creating Comparators this way is a lot easier if you use either Guava or Commons / Lang

Guava Versions:

@Override
public int compare(final Foo a, final Foo b){
    return ComparisonChain
        .start()
        .compare(a.bar(), b.bar())
        .compare(a.baz(), b.baz())
        .result();
}

Commons / Lang Version:

@Override
public int compare(final Foo a, final Foo b){
    return new CompareToBuilder()
        .append(a.bar(), b.bar())
        .append(a.baz(), b.baz())
        .toComparison();
}

(Both of these versions won't fail if any of the values are null, my quick and dirty code above will)

Solve the Problem

I don't think you should do a Binary search in the first place, this seems very complicated.

Why don't you use a TreeSet with a custom comparator? Or Collections.sort(list, comparator)? (For both of these options you can use the comparators I showed earlier).

Also, you should think about letting your Contestant implement Comparable<Contestant>. That way you won't need to use an external Comparator. You can use the same logic as above in the compareTo() method, just replace one of the objects with this.

edited Mar 2, 2011 at 16:20

answered Mar 2, 2011 at 15:44

Sean Patrick Floyd

301k72 gold badges481 silver badges598 bronze badges

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

1 Comment

jtahlborn Over a year ago

Note, the Collections.sort() call is already required in order for the binary search to work in the first place.

Kellindil · Accepted Answer · 2011-03-02 15:48:14Z

0

You might have already tried this, and this solution might not be available to you, but if you can change your "Contestant" class, you can make it extend the "java.lang.Comparable" interface and override Comparable#compareTo(Contestant) method so that it takes both the name and starting number into account. Afterwards, you'll be able to use the Collections.binarySearch(Collection<Contestant>, Contestant) method for your need.

answered Mar 2, 2011 at 15:48

Kellindil

4,53323 silver badges20 bronze badges

Collectives™ on Stack Overflow

using multiple comparators in a java binarySearch

2 Answers 2

One Comparator only

Use Libraries

Solve the Problem

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

One Comparator only

Use Libraries

Solve the Problem

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related