Extend the code in Figure 19.3 on pp. 809811 in the textbook to use a recursive approach to the binary search algorithm. To do this, add a method called that receives the search key, starting index, and ending index as arguments. If the search key is found, return its index in the array, but if the search key is not found, return -1. Add code to the main method to demonstrate that your method works. Ensure that the name of your method includes your last name (e.g., John Doe might use a method name like this: recursiveSearchDoe).

Take a screenshot of your output, showing the current time and date on your screenshot. Copy your screenshot into a new Word document under an Exercise 1 heading.

// Fig. 19.4: BinarySearchTest.java // Use binary search to locate an item in an array. import java.security.SecureRandom; import java.util.Arrays; import java.util.Scanner;

public class BinarySearchTest { // perform a binary search on the data public static int binarySearch(int[] data, int key) { int low = 0; // low end of the search area int high = data.length - 1; // high end of the search area int middle = (low + high + 1) / 2; // middle element int location = -1; // return value; -1 if not found

do // loop to search for element { // print remaining elements of array System.out.print(remainingElements(data, low, high));

// output spaces for alignment for (int i = 0; i < middle; i++) System.out.print(" "); System.out.println(" * "); // indicate current middle

// if the element is found at the middle if (key == data[middle]) location = middle; // location is the current middle else if (key < data[middle]) // middle element is too high high = middle - 1; // eliminate the higher half else // middle element is too low low = middle + 1; // eliminate the lower half

middle = (low + high + 1) / 2; // recalculate the middle } while ((low <= high) && (location == -1));

return location; // return location of search key } // end method binarySearch

// method to output certain values in array private static String remainingElements(int[] data, int low, int high) { StringBuilder temporary = new StringBuilder();

// append spaces for alignment for (int i = 0; i < low; i++) temporary.append(" ");

// append elements left in array for (int i = low; i <= high; i++) temporary.append(data[i] + " ");

return String.format("%s%n", temporary); } // end method remainingElements

public static void main(String[] args) { Scanner input = new Scanner(System.in); SecureRandom generator = new SecureRandom();

int[] data = new int[15]; // create array

for (int i = 0; i < data.length; i++) // populate array data[i] = 10 + generator.nextInt(90);

Arrays.sort(data); // binarySearch requires sorted array System.out.printf("%s%n%n", Arrays.toString(data)); // display array

// get input from user System.out.print("Please enter an integer value (-1 to quit): "); int searchInt = input.nextInt();

// repeatedly input an integer; -1 terminates the program while (searchInt != -1) { // perform search int location = binarySearch(data, searchInt);

if (location == -1) // not found System.out.printf("%d was not found%n%n", searchInt); else // found System.out.printf("%d was found in position %d%n%n", searchInt, location);

// get input from user System.out.print("Please enter an integer value (-1 to quit): "); searchInt = input.nextInt(); } } // end main } // end class BinarySearchTest

/