Postlab 6: Timing Searching Algorithms

In lab 6 you did timings for insertion sort and selection sort. One thing you discovered is that you needed to use different array sizes in different situations to get runtimes that were meaningful but not ridiculously long.

In this postlab you will do timings for sequential search and binary search. We talked about these in class, and code for both is in the Searching class in the text (Listing 9.12). Type in this class and add code to your lab 6 driver to give both searching options. You'll also need to read in the value to search for; remember that one way to get worst-case behavior for both searches is to search for a value that you know is not in the array (e.g., -1). Don't forget that the array must be sorted to do binary search! Do not sort it every time the user selects binary search -- this takes too long -- but remind the user that it should be sorted, and when you run the program remember to sort it once before you do binary search.

Construct tables like the ones from lab 6 to record your timings. Experiment and try to find four consecutive doubling array sizes (e.g., 10, 20, 40, 80) that give useful times for each searching algorithm.

As we discussed in class, there's a problem in that binary search is fast so you'll need to use big arrays in those timings, but the array has to be sorted first and sorting is relatively slow. If you get stuck because of this problem (can't sort a big enough array to get useful times from binary search), try adding an option that constructs an already sorted array -- you can just fill it with integers 1..N, or 1,3,5,7,... or whatever you can easily do in a loop. This will let you use larger arrays.

Explain your results in a file called "" where "xxx" are your initials.