Making Collections.binarySearch() work with compareToIgnoreCase?

Question

So I am searching a huge ArrayList for a particular String value, but I need Collections.binarySearch() to return a value >=0 if the String I am looking for is equal( non case-sensitive) to the String I pass into the binarySearch() method.

Now in the source code for Collections.binarySearch(), it eventually calls the following lines of code.

 Comparable<? super T> midVal = list.get(mid);
 int cmp = midVal.compareTo(key);

So seen as I cannot override String as its final (therefore preventing me from overriding its compareTo() method to call compareToIgnoreCase() ), is there any other I can achieve this?

Any help would be great thanks.

Alex Salauyou · Accepted Answer · 2015-05-12T15:26:49.530

6

To perform case-insensitive binary search, use String::compareToIgnoreCase as a comparator:

int i = Collections.binarySearch(list, key, String::compareToIgnoreCase);

This will perform faster than comparing two strings reduced to the same case, because compareToIgnoreCase() compares chars one by one, reducing case of chars only if needed, which allows to return fast if strings are different in first chars.

NB: To make binarySearch() with this comparator work properly, collection must be sorted using exactly the same comparator:

Collections.sort(list, String::compareToIgnoreCase);

edited May 12 '15 at 15:26

answered May 12 '15 at 13:11

Alex Salauyou

14,185
5
45
67

1

Yes. Also note that in order for this to work, the list must have been sorted using the same comparator. – Stuart Marks May 12 '15 at 15:22
This is for Java 8 though. This is how you do it in Java 7: https://stackoverflow.com/a/17491652/900394 – Alaa M. Jul 04 '20 at 19:51

Steve Chaloner · Answer 2 · 2015-05-12T13:10:04.407

Use an external Comparator, because java.util.Collections has a binarySearch method with this signature:

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

Your comparator would look something like

public class CaseInsensitiveComparator implements Comparator<String> {
    public int compare(String s1, String s2) {
      // check if any of the arguments are null, otherwise
      return s1.toLowerCase().compareTo(s2.toLowerCase());
    }
}

Even if you could extend String to override the compareTo method, I do not think that would be a good idea.

Making Collections.binarySearch() work with compareToIgnoreCase?

2 Answers2

Linked