Linear and Binary Searches

In class, we have discussed both the linear search and the binary search.

1. Write a brief description (a few sentences) of how a linear search works.

2. Write a brief description (a few sentences) of how a binary search works. Be sure to include any assumptions the algorithm makes.

In class, we have discussed how efficient each of these algorithms might be. Now we take a more concrete, experimental approach.

Experiments Regarding Search

We will search for random numbers in a sequence of even integers:

Technically, the structure holding such a collection of data is called an array. With the array data just described, a search should be successful if we are looking for an even, nonnegative integer that is not too large. The search should fail if the desired integer is negative, odd, or too large. In our experiment, we will pick 60 integers as candidates for the search. We pick the first 30 from within the array, to ensure that the search will be successful. Then we then pick the last 30 from the set of odd integers, so that the search will fail. In each case, we will select numbers at random from the given set.

The searchTest program

The program searchTest performs both a linear search and a binary search for randomly-selected items, and records the (approximate) number of comparisons performed by each search algorithm.

The mechanics of running these search experiments are as follows:

• Open a terminal window and move to your 105 directory, with the command:

    cd 105

• Copy the program to your 105 directory, with the command below. (Note that the final period is necessary.)

    cp ~weinman/courses/CSC105/labs/searchTest .

• Run the program with the command:

    ./searchTest

• The program will ask you to enter the size of the sequence to be searched. I suggest you use values in the range from 1000 to 50,000, but you can also choose smaller or larger sizes for the array. The program then will report on each of the 60 trials (values searched for), and give aggregate results for each search algorithm and each search outcome.

  Note: Do not use commas when entering numbers.

• Note: After you run the above command the first time, you can use the up-arrow key at your keyboard to retrieve the same command again. After pressing the up-arrow key to get the desired command, just press Enter to run the program again.

Opening a Spreadsheet

3. Launch the Open Office program. Recall you can do this by clicking on the icon with the blue circle and two white birds on it in your taskbar at the bottom of the screen.

   A window should appear with a dialog box asking what type of new document you would like to create. Click the "Spreadsheet" option. Recall that information in a spreadsheet is arranged in cells. Rows are labeled by numbers (on the left hand margin), and columns are labeled by letters (at the top margin). Cells (or rectangular blocks) then are labeled by a column/row combination.

4. Spreadsheets allow you to enter information by clicking your mouse on any cell and typing data. Click on cell A1. Enter the text "Size", which will indicate the size of the array that will be searched.

   Click on cell B1. Enter the text "Steps", which will indicate the number of steps that the search required.

Collecting Experimental Data

5. Run searchTest for a several (at least 10) array sizes between 1000 and 50,000.

   Use your spreadsheet to record the results from each program run (i.e., for each array size in your experiment). You will need to record:

   1. array sizes and steps for successful searches with linear search,
   2. array sizes and steps for unsuccessful searches with linear search,
   3. array sizes and steps for successful searches using binary search, and
   4. array sizes and steps for unsuccessful searches using binary search.
   To do this, place the sizes and steps for (i) in columns A and B, respectively, the sizes and steps for (ii) in columns C and D, respectively, the sizes and steps for (iii) in columns E and F, respectively, and the sizes and steps for (iv) in columns G and H, respectively.

   Do double-check your data entry! Typographical errors can add more spice than is intended to your results.

6. Now we will the data use your spreadsheet to plot the data for each of the four tables you just created by making a separate graph for each table.

   We will say exactly how to do this in just a moment. To get a sense of how the search algorithm performance varies with array size, The horizontal axis of each of your graphs should indicate the array size, and the vertical axis should indicate the average number of steps required. You should conduct sufficient experiments, so that a fairly consistent pattern emerges.

   Select two of the columns corresponding to the data for one type of search (e.g., columns A and B). In OpenOffice Calc you can create a graph from this data by selecting Chart... from the Insert menu. You will probably find that a "XY (Scatter)" chart is appropriate for this type of data. Once you have selected that, you may also find the subtype called "Points and Lines" to be appropriate. You should also check "Sort by X values."

   As you click through the options with the "Next>>" button, be sure to label the X and Y axes appropriately and title the graph indicating the search algorithm (e.g., linear or binary) and whether the data is for successful or unsuccessful searches.

   Finally, I suggest that you use the same Y-axis scale for each pair of graphs that depict results from the same search algorithm. This will make a visual comparison of the graphs more meaningful. In OpenOffice Calc, you can set the Y-axis scale as follows. Double-click on the chart, then click on the "Format" menu, followed by the "Axis" entry, and finally "Y-axis" from the menu. In the dialogue box that appears, you can uncheck the "Automatic" selection and set both graphs of the search type to the same to the bound.

7. Describe some conclusions you can draw from your experiments. For example, you might compare and contrast the various graphs you have made.