Generic Binary Search Fails Using A Key Of Consecutive Characters

Question

I have a generic binary search that seems to function fine with Integers. However, when I try to use it with Strings it sometimes crashes, presenting a ArrayIndexOutOfBoundsException at various lines; especially I specify the key with a word using the same letter more than once. For example String key = "peach"; returns the correct index, String key = "blueberry"; is not found, and String key = "scoop"; causes a failure. It appears to have to do with (key.equals(list[mid])) in T, but I cannot make sense of it. Thanks for your help.

public class BinarySearch {

private BinarySearch() { }

private static <T extends Comparable<? super T>> int search(T[] list, int first, int last, T key){
    int foundPosition;
    int mid = first + (last - first) / 2;  
    if (first > last)
        foundPosition = -1;
    else if (key.equals(list[mid]))
        foundPosition = mid;
    else if (key.compareTo(list[mid]) < 0)
        foundPosition = search(list, first, mid - 1, key);
    else
        foundPosition = search(list, mid + 1, last, key);

    return foundPosition;
} 

public static void main(String args[]) {

Integer [] a = {0,2,4,6,8,10,12,14,16};
int finalIndex = 9;
System.out.println("Integer test array contains...");
    for (Integer a1 : a) {
        System.out.print(a1 + " ");
    }
int result;
for (int key = -4; key < 11; key++) {
    result = BinarySearch.search(a, 0, finalIndex, key);
    if (result < 0)
        System.out.println("\n" + key + " is not in the array.");
    else
        System.out.println("\n" + key + " is at index " + result + ".");
}

String[] searchFruits = {"lemon", "apple", "banana", "peach", "pineapple", "grapes", "blueberry", "papaya"};   
System.out.println("\nChecking fruits...");
System.out.println("String test array contains...");
 for (String a1 : searchFruits) {
        System.out.print(a1 + " ");
    }
int fruit = 8;
int fresult;
String key = "blueberry";
    fresult = BinarySearch.search(searchFruits, 0, fruit, key);
    if (fresult < 0)
        System.out.println("\n" + key + " is not in the array.");
    else
        System.out.println("\n" + key + " is at index " + fresult + ".");
}

}

Answer 1

So the problem is you are using the size of the array as your index, leading to the array index out of bounds issue.

Specifically

int finalIndex = 9;

and

int fruit = 8;

Now the reason you only see the exception some times depends on which way the binary search goes. If the value you are searching for is < than the middle value it will works its way down the lower half of the index and thus reach zero and never throw an index out of bounds exceptions. However if the value is > than the middle value you will increment till you hit you hit the last value, in this case "8" which will give an index out of bounds.

You need to be decrement your index value by one to account for indexes starting at 0.

Example:

int finalIndex = a.length-1;

int fruit = searchFruits.length-1;