Limited access

Upgrade to access all content for this subject

The following method, binarySearchStrings, performs a recursive binary search to find the index of a specified String from an alphabetized array of Strings:

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

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

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

At each step, the algorithm works by comparing the current String at the mid position to the key value. This comparison is performed using the compareTo method of the String class, which returns 0 if the argument String is alphabetically equal to the calling String, a negative number if the argument String falls after the calling String alphabetically, and a positive number if it falls before. For example:

"A".compareTo("A"); // returns 0
"A".compareTo("B"); // returns -1
"B".compareTo("A"); // returns 1

Using this information about the alphabetical ordering of the key and mid values, the procedure recurses on the half of the list that could alphabetically contain the key. If the key is found, its index is returned, otherwise the procedure returns -1 when it eventually recurses on an empty array.

Using the binarySearchStrings method, you perform the following search:

String[] values = {"alfa", "bravo", "charlie", "delta", "echo", "foxtrot",
                   "golf", "hotel", "india", "juliett", "kilo",
                   "lima", "mike", "november", "oscar", "papa",
                   "quebec", "romeo", "sierra", "tango", "uniform",
                   "victor", "whiskey", "x-ray", "yankee", "zulu"};

int index = binarySearchStrings(values, "echo", 0, values.length - 1);

What is the String at the mid position at each step of the search? In other words, which Strings from the array values are examined in the process of finding the String "echo"? Enter the Strings exactly as they occur in the values array.

Select an assignment template