How do I print all strings from matching indexes in two different ArrayLists using Binary Search?

Question

I have found the matching index between two strings from two different lists using:

index = Collections.binarySearch(aList, bList);

However, there are multiple strings matching the one from aList. I am able to decrement the index to find the very first index match in the bList using:

if (index >= 0 ){

        while (aList.get(index-1) != bList){

            --index;

            break;

        }

However I am only able to find the very first match. All the code I have tried does not work for incrementing from the first match through the last match and outputting the all the strings from each matching index. Is there an approach to this? I would really appreciate your help!

Answer 1

Here’s the corrected and completed version:

    List<String> aList = List.of("Carrot", "Carrot", "Cauliflower",
            "Mushroom", "Mushroom", "Mushroom", "Mushroom", "Pointed cabbage");
    String bItem = "Mushroom";
    int index = Collections.binarySearch(aList, bItem);
    if (index >= 0) {
        int firstIndexInclusive = index;
        while (firstIndexInclusive > 0 && aList.get(firstIndexInclusive - 1).equals(bItem)) {
            firstIndexInclusive--;
        }
        int lastIndexExclusive = index;
        while (lastIndexExclusive < aList.size() && aList.get(lastIndexExclusive).equals(bItem)) {
            lastIndexExclusive++;
        }
        // Print all matching entries
        for (int i = firstIndexInclusive; i < lastIndexExclusive; i++) {
            System.out.println("" + i + ": " + aList.get(i));
        }
    } else {
        System.out.println("Not found");
    }

Output is:

3: Mushroom
4: Mushroom
5: Mushroom
6: Mushroom

What went wrong in your code?

This line has a couple of problems:

    while (aList.get(index-1) != bList){

index may be 0 (sooner or later), and if it is, aList.get(index-1) throws an exception. Comparing with != generally does not work except if bList is a primitive (not a reference type like an object) (and even in that case it’s not the recommended, readable way).

This line is wrong too:

        break;

You are breaking out of the loop after decrementing index once, so if there are more matches to the left, you are not including them.

Finally there is nothing in the code you have shown that finds matches to the right of the index returned by binarySearch().