Binary Search Lab Write a Java program which will use Binary Search to find a na
ID: 3701954 • Letter: B
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
import java.io.IOException;
import java.net.URL;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class NameGuesser {
public static void main(String[] args) {
URL aUrl;
Scanner in = null;
try {
aUrl = new URL("https://www2.census.gov/topics/genealogy/1990surnames/dist.all.last");
in = new Scanner(aUrl.openStream());
} catch (IOException e) {
e.printStackTrace();
}
Scanner sc = new Scanner(System.in);
ArrayList<String> names = new ArrayList<String>();
while (in!=null && in.hasNext()) {
names.add(in.next());
if (in.hasNextLine()) {
in.nextLine();
}
}
Collections.sort(names);
int low = 0;
int high = names.size();
int mid = (high + low) / 2;
while (low < high) {
System.out.println("Does your name come before " + names.get(mid) + " in the dictionary? (Y/N)");
String ans = sc.nextLine();
if (ans.equals("Y")) {
high = mid - 1;
} else if (ans.equals("N")) {
low = mid + 1;
}
else{
System.out.println("Wrong Input Entered.");
break;
}
mid = (low + high) / 2;
}
if (low >= high) {
System.out.println("Is your name " + names.get(mid) + "? (Y/N))");
String ans = sc.nextLine();
if(ans.equals("Y")){
System.out.println("Name Found");
}
else{
System.out.println("Name not Found");
}
}
}
}
/*
Total number of entries : 88799
Time complexity in worst case will be O(log n) for binary search.
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.