Question
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,
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
/
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started