A07

Due Date: Thursday, March 14
File(s) to be submitted: SearchComparisons.java
Sample Output: SampleOutput.html
Starter Files:

• SearchComparisons.java

Comparing Search Methods (Algorithmic Analysis)

Summary

Complete the definitions of the sortedLinearSearch and binarySearch methods in the program SearchComparisons.

Change the seed of the Random object to the last six digits of your A-number. Run the revised code and replace the "expected output" at the bottom of the file with the output your code generated.

NOTE: the version of binary search I used in my sample program was not the same as the (recursive) version in the slides. The numbers you get may be off-by-one from mine (either higher or lower) and still be OK.

Details

The program I have provided is designed to compare three different search methods:

• simple linear search
• sorted linear search
• binary search

You must complete the two remaining search methods.

Use unsortedLinearSearch as your model for the remaining implementations. In particular:

• Note that the method doesn't return where it found the item (as a search method normally would. Instead it returns the count of how many comparisons it needed to do.
• Note that it does increment a counter, found, when it finds an item. (The purpose is to help you make sure that your code is working. The count is printed at the end of each set of tests, and should be either 0, 4800, or around 2400, depending on the test set.)
• Note the two return commands. They both return opCount, as that is what this version of the search method is supposed to do. Normally those return commands would be replaced by return posn; and return -1; Your methods will need to make similar revisions from the pseudo-code provided in the course notes.

The sample output shows the expected results for when you've completed the two method definitions. If you have different results, then you've done something that's either wrong or at least unexpected. Please try to get them to match up.

Once you've got them matching up, replace the seed value for the Random object. It is currently 20240313. I'd like you to change it to the last six digits of your A-number. For example, if your A-number were A00120340, then the seed for you to use would be 120340. The numbers will change with the new seed, but they shouldn't be very different.

Copy the output of your program and replace the bit at the bottom of SearchComparisons.java after the // Expected results line and between the /* and */ lines. (Your code must still compile!)

Submit the revised program with the revised "expected output".