Question

Learning objectives; File I/O practice, exceptions, binary search, recursion. Design and implement a recursive version of a binary search. Instead of using a loop to repeatedly check for the target value, use calls to a recursive method to check one value at a time. If the value is not the target, refine the search space and call the method again. The name to search for is entered by the user, as is the indexes that define the range of viable candidates can be entered by the user (that are passed to the method). The base case that ends recursion is either finding the value within the range or running out of data to search. The program will work on an array of sorted String objects read in from a text file. Your program will generate an exception, that provides a message to the user, if the file can't be found or if the starting index is after the ending index. You will create your own text file of first names in alphabetical order (binary search required ordering) to test your program, make sure to include that file with your submission. JAVA CODE

Answer 1

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class RecursiveBinarySearch {
  
private static int recursiveBinarySearch(String arr[], int leftIndex, int rightIndex, String target)
{
int index = -1;
if(rightIndex >= leftIndex && leftIndex < arr.length - 1)
{
int midIndex = leftIndex + (rightIndex - leftIndex) / 2;
if(arr[midIndex].compareToIgnoreCase(target) == 0)
index = midIndex;
else if(arr[midIndex].compareToIgnoreCase(target) > 0)
index = recursiveBinarySearch(arr, leftIndex, midIndex - 1, target);
else
index = recursiveBinarySearch(arr, midIndex + 1, rightIndex, target);
}
return index;
}
  
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Scanner fileReader;
System.out.print("Enter the input file name: ");
String inFileName = sc.nextLine().trim();
  
// read file to count number of names
int countStrs = 0;
try
{
fileReader = new Scanner(new File(inFileName));
while(fileReader.hasNextLine())
{
String s = fileReader.nextLine();
countStrs++;
}
fileReader.close();
}catch(FileNotFoundException fnfe){
System.out.println(inFileName + " could not be found! Exiting..");
System.exit(0);
}
  
// read all names from input file
System.out.println("\nAttempting to read " + inFileName + "..");
String names[] = new String[countStrs];
int index = 0;
try
{
fileReader = new Scanner(new File(inFileName));
while(fileReader.hasNextLine())
{
names[index++] = fileReader.nextLine().trim();
}
System.out.println(countStrs + " names successfully read from " + inFileName + ".");
fileReader.close();
}catch(FileNotFoundException fnfe){
System.out.println(inFileName + " could not be found! Exiting..");
System.exit(0);
}
  
// sort the array of names in ascending order
for(int i = 0; i < countStrs - 1; i++)
{
for(int j = 0; j < countStrs - i - 1; j++)
{
if(names[j].compareToIgnoreCase(names[j + 1]) > 0)
{
String temp = names[j];
names[j] = names[j + 1];
names[j + 1] = temp;
}
}
}
  
// prompt user to enter the name to search
System.out.println();
String target;
do
{
System.out.print("Enter the target name (quit to stop): ");
target = sc.nextLine().trim();
if(target.equalsIgnoreCase("quit"))
break;
int resultIndex = recursiveBinarySearch(names, 0, countStrs - 1, target);
if(resultIndex == -1)
System.out.println("Sorry! " + target + " is not found in the array.\n");
else
System.out.println(target + " is found at index " + (resultIndex + 1) + ".\n");
}while(!target.equalsIgnoreCase("quit"));
  
}
}

******************************************************* SCREENSHOT *********************************************************

INPUT FILE (names.txt) - This file needs to be created before running the code and this file should be created within the same working project directory where the above RecursiveBinarySearch.java file will be residing.

CONSOLE OUTPUT :

THANK YOU!! PLEASE VOTE