How to perform a binarySearch with a comparator?

Question

I'm trying to perform a binary search with a case-insensitive comparator, but I keep getting errors whatever I try...

Trial 1:

Arrays.binarySearch(arr, "text", String::compareToIgnoreCase);

Source: https://stackoverflow.com/a/30191946/900394

This gives an error:

Method references are not supported at language level '7'

Assuming I want to work with Java 7, I tried these additional methods:

Trial 2:

Comparator<String> caseInsensitiveComparator = new Comparator<String>() {
        @Override
        public int compare(String s, String t1) {
            return s.compareToIgnoreCase(t1);
        }
    };

Arrays.binarySearch(arr, "text", caseInsensitiveComparator);

Source: https://stackoverflow.com/a/14154185/900394

Error:

Required type: Comparator<? super Object>
Provided: Comparator

Note that this method is working for sorting a list (i.e. this comparator is suitable for Collections.sort())

Trial 3:

Arrays.binarySearch(arr, "text", String.CASE_INSENSITIVE_ORDER);

Source: https://stackoverflow.com/a/17491652/900394

Error:

Required type: Comparator<? super Object>
Provided: Comparator

Note that this method is also working on Collections.sort()

Trial 4:

Build a class that implements Comparator<String>:

public class CaseInsensitiveComparatorClass implements Comparator<String> {

    @Override
    public int compare(String s, String t1) {
        return s.compareToIgnoreCase(t1);
    }
}

Arrays.binarySearch(arr, "text", new CaseInsensitiveComparatorClass ());

Source: https://stackoverflow.com/a/30191797/900394

Error:

Required type: Comparator<? super java.lang.Object>
Provided: CaseInsensitiveComparatorClass

Note that this method is also working on Collections.sort()

Can you provide me with one method that does work, or point out what I'm doing wrong?

EDIT:

This is the declaration of arr:

private List<String> lst;

So it's actually a list, which I convert to an array on the method invocation:

Arrays.binarySearch(lst.toArray(),...

I guess issue with type of `arr `. please post how you initialized it — Vasyl Sarzhynskyi, Jul 04 '20 at 13:59
if `arr` declared as `String [] arr`, you shouldn't have a problem — Vasyl Sarzhynskyi, Jul 04 '20 at 14:01
@VasiliySarzhynskyi, it's actually a list, that I convert to an array. Please see edit — Alaa M., Jul 04 '20 at 14:04
you should change code to the following: `Arrays.binarySearch(lst.toArray(new String[0]),...` — Vasyl Sarzhynskyi, Jul 04 '20 at 14:09
@VasiliySarzhynskyi, yep. You're right. Thank you, I chose your answer. Btw I see that all the answers are being downvoted for some reason. I didn't downvote any answer... Don't know what's going on... — Alaa M., Jul 04 '20 at 14:11

score 1 · Accepted Answer · answered Jul 04 '20 at 14:05

1

regarding your first example, you use method reference feature from Java 8 (String::compareToIgnoreCase), but you compile/execute code with Java 7. change version of Java at least to Java 8. also keep in mind, that before using Arrays.binarySearch, your array should be sorted.

for collection you could use the following method: Collections.binarySearch()

in order to convert list to array with generic parameters, use the following:

lst.toArray(new String[0]);

answered Jul 04 '20 at 14:05

Vasyl Sarzhynskyi

3,689
2
22
55

This is the correct answer (converting the list to an array with an explicit type). Thank you. It's strange that the IDE is giving me a totally unrelated error indication. – Alaa M. Jul 04 '20 at 14:10

Joni · Answer 2 · 2020-07-04T14:12:07.043

Instead of an array, you actually have a list: List<String>. Use Collections.binarySearch instead of converting the list to an array followed by Arrays.binarySearch.

List<String> lst = Arrays.asList("a", "text", "z"); // just an example list
int index = Collections.binarySearch(lst, "text", String.CASE_INSENSITIVE_ORDER);

If for some silly reason you must use Arrays.binarySearch, you can pass the concrete list type as an argument to List.toArray. This will make the method return an array of Strings instead an array of Objects:

Arrays.binarySearch(lst.toArray(new String[0]), String.CASE_INSENSITIVE_ORDER)

score 0 · Answer 3 · answered Jul 04 '20 at 14:09

Note that the array should be sorted according to Arrays.binarySearch Javadoc:

Searches the specified array for the specified object using the binary search algorithm. The array must be sorted into ascending order according to the specified comparator (as by the sort(T[], Comparator) method) prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements equal to the specified object, there is no guarantee which one will be found.

The String itself implements Comparable interface, So, there is no need to implement new one

Here is the short code snippet that visualizes how to use Arrays.binarySearch.

public class BinarySearch {
    public static void main(String[] args) {
        final String[] arr = {"one", "two", "three", "four", "text"};

        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        System.out.println(Arrays.binarySearch(arr, "text", String.CASE_INSENSITIVE_ORDER));
    }
}

UPDATE: since you described what arr is type of, you could use Collections.binarySearch. — ngranin, Jul 04 '20 at 14:15

score -1 · Answer 4 · answered Jul 04 '20 at 14:00

Try this code:

    String[] arr = {"a","b","c"};

    int i = Arrays.binarySearch(arr, "B", new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o1.compareToIgnoreCase(o2);
        }
    });

    System.out.println(i);

How to perform a binarySearch with a comparator?

4 Answers4