Extend the code in Figure 19.3 on pp. 809–811 in the textbook to use a recursive
ID: 3817935 • Letter: E
Question
Extend the code in Figure 19.3 on pp. 809–811 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
/
Explanation / Answer
Function for performing recursive binary search is here:
public int recursiveBinarySearch(int[] Arr, int start, int end, int key) {
if (start < end) {
int mid = start + (end - start) / 2;
if (key < Arr[mid]) {
return recursiveBinarySearch(Arr, start, mid, key);
} else if (key > sortedArray[mid]) {
return recursiveBinarySearch(Arr, mid+1, end , key);
} else {
return mid;
}
}
return -1;
}
Add following code to the main method to drive the above function:
public static void main(String[] args)
{
int location = recursiveBinarySearch(data, low, high, searchInt);
if (location == -1) //If element not found
System.out.printf("%d was not found%n%n", searchInt);
else //If element found
System.out.printf("%d was found in position %d%n%n", searchInt, location);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.