?

Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Moderate

Tracking Recursion Depth in a Binary Search

ALGOR-6BWDMU

You are given the following function definition for a recursive binary search:

public int binarySearch(int[] values, int key, int min, int max) {
    if(min > max)
        return -1;

    int mid = min + ((max - min) / 2);

    if(values[mid] < key)
        return binarySearch(values, key, mid + 1, max);
    else if(values[mid] > key)
        return binarySearch(values, key, min, mid - 1);
    else
        return mid;
}

This procedure recursively searches a sorted list to find the index of a specific key value. At each recursive step, the size of the list being searched is reduced by roughly half, until the index of the key is found and returned. If the search terminates without finding the key, a value of -1 is returned to indicate that the key is not contained in the list.

You are also provided with the following array of sorted integers:

int[] values = {2, 4, 5, 5, 6, 10, 13, 25, 26, 29, 40, 47, 67, 70, 72, 88, 93, 95, 96, 99, 100};

Using the binarySearch function, you wish to find the index of the value 13 in this array. You perform the following function call:

int index = binarySearch(values, 13, 0, values.length - 1);