Question

JAVA: 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. 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 the File class
import java.io.FileNotFoundException;  // Import this class to handle errors
import java.util.Scanner; // Import the Scanner class to read text files
import java.util.Arrays;

class Main { 
    static int binarySearch(String[] arr, String x,int l,int r) 
    { 
        int res = -1;
        while (l <= r) { 
            
            int m = l + (r - l) / 2; 
  
            res = x.compareToIgnoreCase(arr[m]); 
  
            if (res == 0){
                System.out.println("name found at "+ "index " + m); 
                System.exit(0);
            }
            if(l == r){
                System.out.println("name not found"); 
                System.exit(0);
            }
  
            // If x greater, ignore left half 
            if (res > 0) 
                binarySearch(arr, x, m+1, r);
  
            // If x is smaller, ignore right half 
            else
                binarySearch(arr, x, l, m-1);
        } 
  
        return -1; 
    } 
  
    // Driver method to test above 
    public static void main(String []args) 
    { 
        String[] arr = {};
        String name = "";
        int l,r;
        try {
          File myObj = new File("names.txt");
          Scanner myReader = new Scanner(myObj);
          while (myReader.hasNextLine()) {
            String data = myReader.nextLine();
            arr = Arrays.copyOf(arr, arr.length + 1);
            arr[arr.length - 1] = data;
          }
          myReader.close();
        } catch (FileNotFoundException e) {
          System.out.println("An error occurred.");
          e.printStackTrace();
        }
        
        Scanner sc = new Scanner(System.in);
        Main obj = new Main();
        System.out.print("Enter name to search:");
        name = sc.nextLine();
        System.out.print("Enter start index:");
        l = sc.nextInt();
        System.out.print("Enter end index:");
        r = sc.nextInt();
            
        int result = obj.binarySearch(arr, name, l, r); 
        if (result == -1) 
            System.out.println("Element not present"); 
    } 
} 

The text file named names.txt is as follows (They are not person names, so change accordingly)

Alabama
Alaska
Arizona
Arkansas
California
Colorado
Connecticut
Delaware
Florida
Georgia
Hawaii
Idaho
Illinois
Indiana
Iowa
Kansas
Kentucky
Louisiana
Maine
Maryland
Massachusetts
Michigan
Minnesota
Mississippi
Missouri
Montana
Nebraska
Nevada
New Hampshire
New Jersey
New Mexico
New York
North Carolina
North Dakota
Ohio
Oklahoma
Oregon
Pennsylvania
Rhode Island
South Carolina
South Dakota
Tennessee
Texas
Utah
Vermont
Virginia
Washington
West Virginia
Wisconsin
Wyoming