Binary Search Lab Write a Java program which will use Binary Search to find a na

Question

Binary Search Lab

Write a Java program which will use Binary Search to find a name within a list of sorted names. This program will read a list of names from a website then guesses a user’s last based on information provided by the user.

To implement this program, create a Java class called NameGuesser. First, implement a main method. The main method will attempt to guess a user’s last name. Before attempting to guess a name, your program must acquire a sorted list of names. Create a new URL object with the following URL

https://www2.census.gov/topics/genealogy/1990surnames/dist.all.last

and use scanner to parse the information contained in the file line by line, discarding the statistical information. Store the parsed information in an ArrayList. After parsing the file at the given URL, sort the ArrayList of names. (Hint, use Collections.sort()) Use the following code snippet to get started.

Scanner in = new Scanner(aUrl.openStream());

Once you have acquired a sorted list of last names, you will begin the process of guessing a user’s last name. You will use a version of binary search for the guessing. Use the following algorithm to implement binary search:

Define three integer variables named low, high, and mid.

At the beginning of the search, set low to 0 and high to the maximum index of the given Linked List.

Set mid to the average of low and high

Ask the use if their name comes before the name stored at index mid in the sorted ArrayList of names

Depending on the answer, update low or high.

If the users name comes after the item at mid, you want to set low to mid + 1

If the users name comes before the item at mid, you want to set high to mid - 1

Repeat this process until low >= high. When low >= high, ask the user if the name at mid is their name.

When you have completed your implementation of the NameGuesser class, use the provided test cases to test your work. When complete, submit your NameGuesser class to Blackboard. Also, in your Blackboard submission, please answer the following questions:

How many entries does your names list have?

How many guesses does your program need to make until it has guessed the user's name or given up? (Use Big-O for your answer.)

Below is an example of what your programs output should look like.

This program tries to guess your last name, but you have to give some hints.

Does your name come before "LANGLITZ" in the dictionary? (Y/N)?

Y

Does your name come before "DURSO" in the dictionary? (Y/N)

Y

Does your name come before "BURROWS" in the dictionary? (Y/N)

N

....?

Is your name "DUKE"? (Y/N)

Y

Explanation / Answer

NameTester.java

import java.io.IOException;
import java.net.MalformedURLException;

public class NameTester {

   public static void main(String[] args) throws MalformedURLException, IOException {
       NameGuesser guesser = new NameGuesser();
       guesser.readNames(); //read and guess the names
       System.out.println(guesser.guessName());
   }

}

NameGuesser.java
import java.io.IOException;
import java.net.MalformedURLException;
import java.net.URL;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class NameGuesser {
   private ArrayList<String> lastNames = new ArrayList<String>();

   public void readNames() throws IOException, MalformedURLException {
       // Read the last names

       URL url = new URL(
               "http://www2.census.gov/topics/genealogy/1990surnames/dist.all.last");

       Scanner in = new Scanner(url.openStream());
       while (in.hasNext()) {
           // Read the last name
           String lastName = in.next();
           lastNames.add(lastName);

           // Ignore the statistical information
           in.nextDouble();
           in.nextDouble();
           in.nextInt();
       }
       in.close();

       // Print out the number of names in the file and
       // Sort the names using Collections
       Collections.sort(lastNames);
       System.out.println("There are " + lastNames.size() + " names in this list");
   }

   public int guessName() {
       int counter = 0;
       int low = 0;
       int high = lastNames.size();
       int mid = high / 2;
       boolean notFound = true; //variables to hold game info
       Scanner input = new Scanner(System.in);
       String userInput = "";
       while (notFound) { //while the name is not found
           System.out.println("Does your name come before " + lastNames.get(mid) + " in the dictionary? (Y/N), or is " + lastNames.get(mid) + " your name? (S)");
           userInput = input.next(); //ask if it is in the middle
           if (userInput.equalsIgnoreCase("Y")) { //if before, set new upper bound
               high = mid;
               mid = ((high - low)/2) + low;
               counter++;
           } else if(userInput.equalsIgnoreCase("N")){ //if after, set new lower bound
               counter++;
               low = mid;
               mid = ((high - low)/2) + low;
           }
           else{ //if name is found, return counter
               System.out.println("Your name, " + lastNames.get(mid) + ", was found with " + counter + " guesses.");
               input.close();
               return counter;
           }
           if(high == low){ //if upper and lower bounds are equal
               System.out.println("Is your name: " + lastNames.get(mid) + " ? (Y/N)");
               userInput = input.next(); //ask if name is found
               if(userInput.equalsIgnoreCase("Y")){ //if yes, print success, counter, and return counter
                   System.out.println("Your name, " + lastNames.get(mid) + ", was found with " + counter + " guesses.");
                   input.close();
                   return counter;
               }
               else if(userInput.equalsIgnoreCase("N")){ //if no, inform user that guesser failed
                   System.out.println("Name not found. Attempted locating with " + counter + " guesses");
                   input.close();
                   return counter;
               }
           }
       }
       input.close();
       return counter;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.