We strongly recommend that you create a top-down design with a fully fleshed out main and stubs for all other functions. However, you may not work with a partner on this lab. Also you don’t need to get approval from an instuctor for your design, though we’d be glad to review it with you in lab, office hours, or ninja sessions. You should only begin implementing the other functions after you have a clear plan in place for the structure of main.

Avoid duplicating similar code in multiple places throughout the program. Think about how you could re-use the same function. For example, we are doing two types of searchs (by location and by name), but the results of those searches are displayed in exactly the same way. Consider having a function that takes in a list of search results and displays them. Then you could call this function for either type of search.

We want the results of our searches to be nicely displayed in the terminal window. However, some hospital names (and city names) are quite long. We can use slicing to truncate these strings to a fixed maximum length, allowing us to create an easy to read table format. This section of the online textbook explains how to slice a string.

The version of linear search that we discussed in class stops as soon as it finds the item it is looking for, and returns the index of that item or -1 if not found. For this problem, your linear search will need to accumulate a list of matching results and return that.

In addition, the basic version of linear search assumes that you are searching a flat list. We will be searching a list of lists, so will need to adapt linear search to use double indexing to get at the data within each sublist.

Because the hospital data is sorted by hospital name we can use binary search to very quickly locate a particular name. However, hospital names are quite long, and users may not know the exact name. So instead of searching for the full name, we will allow users to search using a prefix.

To see if a string begins with a particular prefix, the syntax is: <string>.startswith(<prefix>) which will return True or False.

For example, there are quite a few hospitals that start with "Mary" as shown below:

You should modify binary search so that it uses startswith rather than == to find name matches. However, things get interesting once you find a match. Binary search will inform you of the index of the first match it finds, but there might be more matches just before that index and just after that index. So you’ll need to search in the vicinity of that location to find all of the other potential matches.

For example, suppose that the first match it finds for "Mary" is the one indicated above. You’ll need to search backward from there until you find a name that does not begin with that prefix and you’ll need to search forward from there until you find a name that doesn’t begin with that prefix. You should accumulate all of those hospitals and display their information.