## 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 "SearchingCompare.xxx" where "xxx"
are your initials.