I am trying to implement a recursive binary search algorithm in Java.

I am looking for a string in a ordered array of strings.

Why do i get ArrayIndexOutOfBoundsException with the input "eeeeee", but not with "eeeee"?

Thank you in advance.

import java.util.Scanner;

class binarySearch{
    public static boolean recursiveBinarySearch(String[] arr, String searchTerm, int start, int end){
        int middle = start   (end-start)/2;
        if(start > end){
            return false;
        }

        if(arr[middle].equals(searchTerm)){
            return true;
        } else if(arr[middle].compareTo(searchTerm) > 0){
            return recursiveBinarySearch(arr, searchTerm, start, middle-1);
        } else if(arr[middle].compareTo(searchTerm) < 0){
            return recursiveBinarySearch(arr, searchTerm, middle 1, end);
        }
        return false;
    }

    public static void main(String[] args){

        Scanner console = new Scanner(System.in);
        String[] saved = {"aaaa","bbbb","cccc","ddddd","eeeee"};
        String searchTerm = "";
        do{
            System.out.println("Term to search in the ordered array:");
            searchTerm = console.nextLine();
        } while(searchTerm.equals(""));
        console.close();
        if(recursiveBinarySearch(saved, searchTerm, 0, saved.length)){
            System.out.println("Term found!");
        } else {
            System.out.println("Term NOT found!");
        }
    }
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5

CodePudding user response：

You're passing in end as saved.length. The issue here is that .length will give you the length counting from 1, whereas arrays work with 0.

Just pass in saved.length-1 as end in recursiveBinarySearch, and you're good!

import java.util.Scanner;

class binarySearch{
    public static boolean recursiveBinarySearch(String[] arr, String searchTerm, int start, int end){
        int middle = start   (end-start)/2;
        if(start > end){
            return false;
        }

        if(arr[middle].equals(searchTerm)){
            return true;
        } else if(arr[middle].compareTo(searchTerm) > 0){
            return recursiveBinarySearch(arr, searchTerm, start, middle-1);
        } else if(arr[middle].compareTo(searchTerm) < 0){
            return recursiveBinarySearch(arr, searchTerm, middle 1, end);
        }
        return false;
    }

    public static void main(String[] args){

        Scanner console = new Scanner(System.in);
        String[] saved = {"aaaa","bbbb","cccc","ddddd","eeeee"};
        String searchTerm = "";
        do{
            System.out.println("Term to search in the ordered array:");
            searchTerm = console.nextLine();
        } while(searchTerm.equals(""));
        console.close();
        if(recursiveBinarySearch(saved, searchTerm, 0, saved.length-1)){
            System.out.println("Term found!");
        } else {
            System.out.println("Term NOT found!");
        }
    }
}  

CodePudding user response：

Arrays index goes from 0 to 4, and you pass it saved.length, which has a value of 5. It does not fail with "eeeee" because the code finds the item in the array before reaching the error. Change the line to saved.length-1.