Question

JAVA: Design and implement a recursive version of a binary search.  Instead of using a loop to...

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.

Homework Answers

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

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
IN JAVA Iterative Linear Search, Recursive Binary Search, and Recursive Selection Sort: <-- (I need the...
IN JAVA Iterative Linear Search, Recursive Binary Search, and Recursive Selection Sort: <-- (I need the code to be written with these) I need Class river, Class CTRiver and Class Driver with comments so I can learn and better understand the code I also need a UML Diagram HELP Please! Class River describes river’s name and its length in miles. It provides accessor methods (getters) for both variables, toString() method that returns String representation of the river, and method isLong()...
This assignment involves using a binary search tree (BST) to keep track of all words in...
This assignment involves using a binary search tree (BST) to keep track of all words in a text document. It produces a cross-reference, or a concordance. This is very much like assignment 4, except that you must use a different data structure. You may use some of the code you wrote for that assignment, such as input parsing, for this one. Remember that in a binary search tree, the value to the left of the root is less than the...
language: JAVA the Problem Below are a series of problems you need to solve using recursive...
language: JAVA the Problem Below are a series of problems you need to solve using recursive methods. You will write a program that will read commands from an input file, with each command referring to one of the recursive problems to be executed. Each command will be followed (on the same line of input) by the respective parameters required for that problem. (15 points for main method) DescArrayCheck   Write a recursive method that checks whether an array of integers -...
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
Please answer in JAVA IDS 401 Assignment 4 Deadline In order to receive full credit, this...
Please answer in JAVA IDS 401 Assignment 4 Deadline In order to receive full credit, this assignment must be submitted by the deadline on Blackboard. Submitting your assignment early is recommended, in case problems arise with the submission process. Late submissions will be accepted (but penalized 10pts for each day late) up to one week after the submission deadline. After that, assignments will not be accepted. Assignment The object of this assignment is to construct a mini-banking system that helps...
C PROGRAMMING Doubly Linked List For this program you’ll implement a doubly linked list of strings....
C PROGRAMMING Doubly Linked List For this program you’ll implement a doubly linked list of strings. You must base your code on the doubly linked list implementation given in my Week 8 slides. Change the code so that instead of an ‘int’ each node stores a string (choose a suitable size). Each node should also have a next node pointer, and previous node pointer. Then write functions to implement the following linked list operations: • A printList function that prints...
Objectives:The focus of this assignment is to create and use a recursive method given a moderately...
Objectives:The focus of this assignment is to create and use a recursive method given a moderately difficult problem. Program Description: This project will alter the EmployeeManager to add a search feature, allowing the user to find an Employee by a substring of their name. This will be done by implementing the Rabin-Karp algorithm. A total of seven classes are required. Employee (From previous assignment) HourlyEmployee (From previous assignment) SalaryEmployee (From previous assignment) CommissionEmployee (From previous assignment) EmployeeManager (Altered from previous...
STRICT DOWNVOTE IF NOT DONE FULLY, WILL REPORT ALSO IF COPY PASTED OR MODIFIED ANSWER Develop...
STRICT DOWNVOTE IF NOT DONE FULLY, WILL REPORT ALSO IF COPY PASTED OR MODIFIED ANSWER Develop a class, using templates, to provide functionality for a set of recursive functions. The functions specified as recursive must be written recursively (not iterativly). The UML class specifications are provided below. A main will be provided. Additionally, a make file will need to be developed and submitted. ● Recursion Set Class The recursion set template class will implement the template functions. recursionSet -length: int...
Objective The Final Project aims to demonstrate your ability to analyze data from a big database,...
Objective The Final Project aims to demonstrate your ability to analyze data from a big database, exercise use of arrays of objects, external classes, processing files and user interaction. For this project, you will design and implement a program that analyzes baby name popularities in data provided by the Social Security Administration. Every 10 years, the data gives the 1,000 most popular boy and girl names for kids born in the United States. The data can be boiled down to...
I've posted this question like 3 times now and I can't seem to find someone that...
I've posted this question like 3 times now and I can't seem to find someone that is able to answer it. Please can someone help me code this? Thank you!! Programming Project #4 – Programmer Jones and the Temple of Gloom Part 1 The stack data structure plays a pivotal role in the design of computer games. Any algorithm that requires the user to retrace their steps is a perfect candidate for using a stack. In this simple game you...