Question

JAVA CODE

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.  

Just a reminder, don’t forget to submit all the required files and screenshots, including multiple runs showing both finding and not finding a name, an example of your exception being thrown and the message displayed for indices not within range, and the data file that you used. You should have used at least 30 first names to effectively demonstrate a binary search starting between indices.

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"));

 Â

}

}

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.