Ace the AP Computer Science Exam for High Schoolers/

...

/

Solution Review: Recursive Binary Search

Solution Review: Recursive Binary Search

Have a look at the solution to the 'Recursive Binary Search' challenge.

We'll cover the following...

Rubric criteria

Solution

Java
class BinarySearch
{
    public static int search(int[] array, int left, int right, int value)
    {
        if(right >= left)
        {
            int middle = (left + right)/2;
            if (array[middle] == value)     // second base case
                return middle;
            else if(array[middle] > value)  // first recursive case
                return search(array, left, middle-1, value);
            else                            // second recursive case
                return search(array, middle+1, right, value);
        }
        else                               // first base case
            return -1;
    }
    public static int binarySearch(int[]array, int value)
    {
        return search(array, 0, array.length-1, value);    // calling recursive method
    }
    public static void main(String args[]) 
    {
        int[] array = {1, 2, 3, 4, 5, 6};
        System.out.println( binarySearch(array, 5) );
    }
}

Rubric-wise explanation

According to the problem statement, a call from the main function will send the array and a value that is to be found. Look at line 22. We create the header of a binarySearch() function. It takes array and value as input and returns the position of value in array. In this function, we call another method: search.

Point 1:

The search method is a recursive method. To carry out the recursion ...