There are many faculty and staff on campus who you might want to interact with, but finding everyone can be a challenge! In this part of the lab, we will create an application that creates a list of contact information for each faculty and staff member in the College including their office number, then we will use that list to allow users to look up peoples’ office numbers based on their names.
To make the application as fast as possible with lists, we will maintain the list in sorted order (based on peoples’ names), then use the binary search algorithm to find a person, based on the input from a user.
For each faculty and staff member in the College directory, we will maintain a Contact object, where the Contact class simply has two instance variables: name, storing the person’s full name (recorded as <last name>, <first name>, e.g., Eck, Adam) and office, storing the location of their office (e.g., King 125B). We have provided you with a FacultyStaff.txt file in your GitHub repository that contains all of this information.
To keep our list of Contacts sorted, we will use the selection sort algorithm. Its pseudocode is:
i of your list of Contacts from 0 to size() - 1 [inclusive]
Contact with the earliest name in alphabetical order from index i to the end of the list of Contacts.Contact at position i with the Contact found in Step (1a) above.Hint
Our sorting algorithm compares the names of different Contacts, but we cannot simply use the < operator to decide if one name String is earlier in alphabetical order than another String (like we could in Python and some other languages). Instead, in Java, we use the compareTo(String other) method for String objects – calling s1.compareTo(s2):
0) if s1 is earlier in alphabetical order than s20 if s1 and s2 are the same String0) if s1 is later in alphabetical order than s2If our list is in sorted order, then we can quickly find an item using an algorithm called binary search. The iterative (i.e., non-recursive) version of that algorithm (similar to the GuessingGame in Lab 1 works as follows:
min equal to 0 and max equal to the size() of the listmin <= max and we have not found the user’s input name
Contact in the middle of the list between min and maxname of the Contact from Step (3a) starts with the input name the user is searching for from Step 1 (using the startsWith(String prefix) method of the String class). If yes, return this Contactname of the Contact from Step (3a), then search earlier in the list by assigning max to be one index before the middle index computed in Step (3a)name of the Contact from Step (3a), then search later in the list by assigning min to be one index after the middle index computed in Step (3a)Steps 3c and 3d cut the remaining list to search in half each time, drastically reducing the total number of comparisons needed to find a name in the list when compared to starting at the beginning and looking at each Contact until the one wanted by the user is found.
We have provided you with a class Contact that you can use to store the name and office location for each faculty and staff member in the FacultyStaff.txt file.
Inside your GitHub repository, open the file called ContactApp.java in Visual Studio Code. In this file, create a new class ContactApp. Within this class, you should implement a program that accomplishes the following:
FacultyStaff.txt file and save them to a MyArrayList of Contacts. That MyArrayList should be the only instance variable of the ContactApp class.Hint
Each line of the FacultyStaff.txt file represents a different faculty or staff person. Each line is formatted as “name” tab “office location”. You can parse each line String by using the split method of the String class:
String[] splitLine = line.split("\t");
where the name will be in the first index of splitLine and the office will be in the second index of splitLine. Here, “\t” represents a tab in the String.
ReadMe
To earn full credit, you should use your MyArrayList to complete this part of the lab. However, if your MyArrayList is not quite working, you can still earn partial credit by using Java’s built in ArrayList class since one of the goals of this part is to gain practice using array lists to solve interesting real-world problems.
Contacts in the MyArrayList so that the Contacts are in alphabetical order by the name of each ContactMyArrayList of Contacts until the user chooses to end the program by typing the input exit.
Contact whose name starts with the input given by the user. If a Contact is found, you should print their office location followed by their name in parentheses. For example: King 125B (Eck, Adam)Contact can be found by binary search, then the program should print a message saying the requested person cannot be found.You should create methods for each of these major components of your program. The logical flow of your program (e.g., calling the methods in the correct order) should be implemented in the public static void main(String[] args) method of your class.
ReadMe
Since our binary search pseudocode above instructs to check whether a Contact’s name starts with the input from the user, the name found by our application might not be exactly the name the user was looking for. For example, there are 8 names in the FacultyStaff.txt file that start with Ch, so if the user searches for Ch, the application will print the first name it finds that starts with Ch (which may not be the first in alphabetical order given that the algorithm starts searching in the middle of the list of Contacts).
You should find that the longer the user’s search String, the more likely your application is to find the requested person (instead of someone with a similar name).
To help with debugging, here are some possible outputs of your program:
What name would you like to search for? (Type exit to quit) Eck
The office found is: King Building 125B (Eck, Adam)
What name would you like to search for? (Type exit to quit) Hoyle
The office found is: Rice Hall 108 (Hoyle, Roberto)
What name would you like to search for? (Type exit to quit) Draper
The office found is: King Building 125A (Draper, Lucas)
What name would you like to search for? (Type exit to quit) Wang
The office found is: King Building 223D (Wang, Emily)
What name would you like to search for? (Type exit to quit) Levinson
The office found is: King Building 139C (Levinson, Howard)
What name would you like to search for? (Type exit to quit) Nobody
Sorry, but we could not find the name: Nobody
What name would you like to search for? (Type exit to quit) exit
Don’t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.