Assignment Goals
[Note - I was planning on doing another part to this where we used binary search to go through a big list of cities to find an autocomplete match - I decided to make this a little smaller assignment this week.]
This assignment explores the power of binary search. You will
- analyze the performance of binary search in comparison to sequential search
- prepare materials discussing the performance
This assignment also differs from the last few in that you will be working on a more complete program, where the different methods in a class work together to solve a larger problem. This is in contrast to the last assignments, where methods solve individual problems tested from main.
Getting Started
Make a package a5. To this package, addSearchTest.java(Links to an external site.)with starter code for the assignment. You will want to carefully read the comments in this file to see where you need to add code.
Search Experiment
In this assignment you will measure the relative performance of binary search and sequential search on different length arrays. The basic idea is to make an array of random values, sort them, and then compare the performance of binary search and sequential search by searching for different key values.
There are many ways to compare performance. For example, the amount of time spent getting an answer is one way. However, even this simple measure has complications. For example, if part of the experiment is run while playing a game on the same computer, this can distort results. Another issue is that code can run so fast on a computer that it is difficult to capture meaningful timings.
Instead, you will use a simple measure - the number of times a the search loop iterates while searching for the key. This is related to the execution time.
Example binary search and sequential search are implemented in the starter code file. Your job is to copy and modify those so they do not return an index value, but instead the number of times the search loop iterates.
Then, write code in the specified methods to use an array of test data, pick a random key, and search for that key. Since the randomness makes it possible for a particular search to find the key the first time it looks, the experiment code repeats the process of picking a random key and counting the search steps for a number of times. Finally, the results are averaged and returned to main, where the results are summarized. In main, add a loop to report results for different length arrays.
For example, a (very small) test array might look like
[1, 2, 4, 4, 5]
If the number of tests to be run is 3, you would run binary search on that array for three randomly chosen keys, like 1, 4, and 5. Then you would run sequential search for the same array for three randomly chosen keys, like 2, 1, 5. If the number of tests to be run is large enough, the specific keys are not likely to change the results.
You will count up the iterations for each key, add them up, and divide by the number of tests to get an average.
Then, repeat the process for a different-sized array.
You will have to generate random numbers for this. There is an example in the code, and you also made random numbers in Lab 4. Please refer to those instructions or resources from the Internet to remind yourself how that works.
Decide what different sizes of arrays will provide insight into the relative performance of the search techniques. In addition, the bigger the repetitions value, the more accurate the average will be - something like a 100 repetitions is probably fine for this experiment. Record the average for each method in a table with the type of search, the size of the array, and average search count.
Write up a short document in a word processing system (Google docs, MS Word, laTEX) showing the table and a graph where the x axis is the length of the array and the y axis is the average iterations for that size array. Then discuss why you chose the array sizes you tested and what trends you see in the experimental data. A paragraph is likely a reasonable length for discussion. Add your name, assignment, and class to the document. Create a pdf (usually a "Save as" or "Print to" pdf is a mechanism to do that) called SearchReport.pdf.
You do not need to write tests for this assignment. However, you should be carefully checking your code using prints or informal tests that you will remove before submitting. You should interpret the table and graph to see if they make sense given what you know of the behavior of these search approaches.