Homework SourseExercise 1 Extend the code in Figure 194 below to use a recu
Exercise 1
Extend the code in Figure 19.4 below. 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
Solution
import java.security.SecureRandom;
import java.util.Arrays;
import java.util.Scanner;
public class Binarysearch {
// 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);
//enter the key to be searched
System.out.printf(\"enter key to be searched by recursive method: \");
int n = input.nextInt();
// call the recursive function
int index = recursiveSearch(data, n,0,data.length);
System.out.println(index);
// get input from user
System.out.print(\"Please enter an integer value (-1 to quit): \");
searchInt = input.nextInt();
}
} // end main
private static int recursiveSearch(int[] data, int key, int start, int end) {
if (start < end) {
int mid = start + (end - start) / 2;
if (key < data[mid]) {
return recursiveSearch(data,key,start, mid);
} else if (key > data[mid]) {
return recursiveSearch(data, key,mid+1, end);
} else {
return mid;
}
}
return -1;
}
} // end class BinarySearchTest
