find a method with the following header:

/** * Performs binary search to find the index of an element, or -1 if * the element is not in the list. * * @param str String to look for * @param list List to search * @precond list is in ascending sorted order (smallest to largest) * @postcond prints the count of the number of steps taken to the screen * @return -1 if str is not in list, or the index of any occurrence of * str if it is in the list. */ public static int binarySearch(String str, List list)

Ignore the @postcond for a moment and focus on the @return. Use the notes from this week's lectures to implement binary search so that it returns back the correct index of the first value and make sure it passes the unit tests given with this project.

Step 2:

Note that we gave you a main method for the lab. If you need to change it to test your code that's great, but once your code is working you should restore the main method and change all of the calls to linearSearch so that they call binarySearch instead, and also so that the list created is in alphabetical order. You can paste in the code below or just make the changes:

public static void main(String[] args) { List list = Arrays.asList("james","market","ran","the","to"); System.out.println("Looking for to"); int idx = binarySearch("to",list); System.out.println("to found at index "+idx); System.out.println(); System.out.println("Looking for market"); idx = binarySearch("market", list); System.out.println("market found at index "+idx); System.out.println(); System.out.println("looking for monday"); idx = binarySearch("monday",list); System.out.println("monday found at index "+idx); }

Once you have completed the first part if you run that modified main method you should see the following as output:

Looking for to to found at index 4 Looking for market market found at index 1 looking for monday monday found at index -1

For the second part of this lab, you will need to modify your binarySearch method so that it prints out the number of comparisons being made at each step. After making these changes if you run the main method you should see the following output:

Looking for to Comparing ran and to 1 comparisons Comparing the and to 2 comparisons Comparing to and to 3 comparisons to found at index 4 Looking for market Comparing ran and market 1 comparisons Comparing james and market 2 comparisons Comparing market and market 3 comparisons market found at index 1 looking for monday Comparing ran and monday 1 comparisons Comparing james and monday 2 comparisons Comparing market and monday 3 comparisons monday found at index -1

Visually inspect your output to make sure it matches the above before moving forward.

Step 3:

In the project folder there is a file named wordlist.txt Open it up in a text editor and review it - you will see that it is a list of 3399 "words" extracted from the Project Gutenberg text of the children's classic The Wonderful Wizard of Oz(Links to an external site.). Many of these are nonsense words and just strings of characters but they are all unique and in order.

First - rewrite the main method so that it loads the words from that file into a List of Strings. Refer to Week 0 module for I/O File processing review if needed.

Next - write code in your main method that uses both your linearSearch and binarySearch methods find how many comparisons it takes to find the following words in the list:

abundance important key thin zoos

Report in the comments at the top of your code how many comparisons it takes to find each of these words with both linear and binary search, as well as what their indexes are in the list (note that they should be the same index reported for both algorithms, but the number of steps will be very different).

Step 4:

Finally think for a bit about both algorithms. What is the best case scenario for both algorithms? What is the worst case? Report in your comments an example word that represents the best case for both algorithms and an example word that represents the worst case for both algorithms, along with a reason why it is the best/worst case.