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 users 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 users 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 users 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.

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

o 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

IMPORTANT NOTE-

what to do the name at mid is the users name (the name being searched for). I request you modify your program so that "If the users name is the item at mid, alert the user and terminate the program". You can achieve this behavior by modifying your programs output to the following:

Does your name come before "*nameAtMid*" in the dictionary? (Y/N)?(If your name is "*nameAtMid*", please enter D to the console)

If the user inputs D, alert the user and terminate the program. Second, rather than repeating the binary search process until low >= high, please repeat the process until low > high.

GIVEN TEST CLASS.

import static org.junit.Assert.*;

import java.io.ByteArrayInputStream;

import java.io.ByteArrayOutputStream;

import java.io.InputStream;

import java.io.PrintStream;

import org.junit.After;

import org.junit.Before;

import org.junit.Test;

public class NameGuesserTest {

private final ByteArrayOutputStream outContent = new ByteArrayOutputStream();

private final ByteArrayOutputStream errContent = new ByteArrayOutputStream();

@Before

public void setUpStreams() {

System.setOut(new PrintStream(outContent));

System.setErr(new PrintStream(errContent));

}

@Test

public void testSMITH() {

//Pass an input into the console and then execute the main method of the program

String input = "N N Y N Y N Y N N N Y Y Y Y D ";

InputStream in = new ByteArrayInputStream(input.getBytes());

System.setIn(in);

NameGuesser.main(null);

String rawOutput = outContent.toString();

String[] splitOutput = rawOutput.split(" ");

assertEquals("When looking at the number of guesses needed, we",15,splitOutput.length-1);

String[] allGuesses = {"LANGLITZ","RITCHIE","SWAGGER","SHANKLIN","SPANO","SIRIANNI","SNAVELY","SLAGTER","SLUSARSKI","SMISEK","SMOLSKI","SMITS","SMITHEY","SMITHEE","SMITH"};

for(int i = 0; i < allGuesses.length; i++) {

assertEquals("When checking if guess " +(i+1)+ " was " + allGuesses[i] + " we",true,splitOutput[i].contains(allGuesses[i]));

}

}

@Test

public void testWHITTEN() {

//Pass an input into the console and then execute the main method of the program

String input = "N N N N Y N N N Y Y N N N Y Y D ";

InputStream in = new ByteArrayInputStream(input.getBytes());

System.setIn(in);

NameGuesser.main(null);

String rawOutput = outContent.toString();

String[] splitOutput = rawOutput.split(" ");

assertEquals("When looking at the number of guesses needed, we",16,splitOutput.length-1);

String[] allGuesses = {"LANGLITZ","RITCHIE","SWAGGER","VESEY","WIKER","WARRING","WERKHOVEN","WHITEHORN","WICKS","WHITTING","WHITLEDGE","WHITSELL","WHITTEMORE","WHITTENTON","WHITTENBECK","WHITTEN"};

for(int i = 0; i < allGuesses.length; i++) {

assertEquals("When checking if guess " +(i+1)+ " was " + allGuesses[i] + " we",true,splitOutput[i].contains(allGuesses[i]));

}

}

@Test

public void testCRAIG() {

//Pass an input into the console and then execute the main method of the program

String input = "Y Y N Y N N N N Y N N N N Y D ";

InputStream in = new ByteArrayInputStream(input.getBytes());

System.setIn(in);

NameGuesser.main(null);

String rawOutput = outContent.toString();

String[] splitOutput = rawOutput.split(" ");

assertEquals("When looking at the number of guesses needed, we",15,splitOutput.length-1);

String[] allGuesses = {"LANGLITZ","DURSO","BURROWS","CREST","CHERNEY","COLLELO","CORNFORTH","COUSER","CRAIGWELL","COWLEY","CRABBE","CRAFTER","CRAGUN","CRAIGER","CRAIG"};

for(int i = 0; i < allGuesses.length; i++) {

assertEquals("When checking if guess " +(i+1)+ " was " + allGuesses[i] + " we",true,splitOutput[i].contains(allGuesses[i]));

}

}

@Test

public void testSINGLETARY() {

//Pass an input into the console and then execute the main method of the program

String input = "N N Y N Y Y N N N N Y Y Y N Y D ";

InputStream in = new ByteArrayInputStream(input.getBytes());

System.setIn(in);

NameGuesser.main(null);

String rawOutput = outContent.toString();

String[] splitOutput = rawOutput.split(" ");

assertEquals("When looking at the number of guesses needed, we",16,splitOutput.length-1);

String[] allGuesses = {"LANGLITZ","RITCHIE","SWAGGER","SHANKLIN","SPANO","SIRIANNI","SHREWSBERRY","SIGNS","SIMMERS","SINGEWALD","SINQUEFIELD","SINISCALCHI","SINGLTON","SINGLER","SINGLETERRY","SINGLETARY"};

for(int i = 0; i < allGuesses.length; i++) {

assertEquals("When checking if guess " +(i+1)+ " was " + allGuesses[i] + " we",true,splitOutput[i].contains(allGuesses[i]));

}

}

@Test

public void testALVEREZ() {

//Pass an input into the console and then execute the main method of the program

String input = "Y Y Y Y Y D";

InputStream in = new ByteArrayInputStream(input.getBytes());

System.setIn(in);

NameGuesser.main(null);

String rawOutput = outContent.toString();

String[] splitOutput = rawOutput.split(" ");

assertEquals("When looking at the number of guesses needed, we",6,splitOutput.length-1);

String[] allGuesses = {"LANGLITZ","DURSO","BURROWS","BELLINGHAM","ASHTON","ALVEREZ"};

for(int i = 0; i < allGuesses.length; i++) {

assertEquals("When checking if guess " +(i+1)+ " was " + allGuesses[i] + " we",true,splitOutput[i].contains(allGuesses[i]));

}

}

@After

public void cleanUpStreams() {

System.setOut(null);

System.setErr(null);

}

}