Sample Run
assignment description
This file shows the expected output
of the SearchComparisons program
after the search routines have been completed.
when the Random object is initialized using the seed 20240313.
The output is provided
so that you can compare your results to mine.
Normally you would initialize the Random object
without a seed.
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.
I have provided numbers from an alternate version of the program
in the sample below -- red text after the number.
If your code matches either the original
or the alternate version,
you should be fine.
Comparing Search Methods
========================
This program compares the simple linear search, sorted linear search, and
binary search.
The results are presented in three tables:
- failed searches.
- successful searches.
- c.50/50 split of failed and successful searches.
The table show the comparison counts for different length lists. For each
length, 100 tests were run, and the number in each column is the average
number of comparisons required for that length and that kind of search.
By Mark Young (A00000000)
...press enter...
Comparison Counts for Failed Search
-----------------------------------
Length Unsorted Sorted Binary
------ -------- ------ ------
2 2 2 2
4 4 3 2
8 8 5 3
16 16 9 4
32 32 17 5
64 64 36 6
128 128 69 7
256 256 134 8
512 512 235 9
1024 1024 523 10
2048 2048 1010 11
4096 4096 2169 12
8192 8192 4012 13
16384 16384 8720 14
32768 32768 15710 15
65536 65536 30381 16
found 0 items in 4800 searches (0%).
...press enter...
Comparison Counts for Successful Search
---------------------------------------
Length Unsorted Sorted Binary
------ -------- ------ ------
2 2 1 2 or 1
4 3 3 2
8 5 4 3
16 8 9 3
32 15 17 4
64 32 31 5
128 61 69 6
256 121 131 7
512 270 265 8
1024 524 506 9
2048 1038 1068 10
4096 2063 2129 11
8192 4134 4301 12
16384 8689 8056 13
32768 16641 16234 14
65536 33816 32720 15
found 4800 items in 4800 searches (100%).
...press enter...
Comparison Counts for 50% Successful Search
-------------------------------------------
Length Unsorted Sorted Binary
------ -------- ------ ------
2 2 2 2
4 3 3 2
8 6 5 3
16 13 9 4
32 24 19 5
64 48 33 6
128 89 61 6
256 200 139 8 or 7
512 389 271 9
1024 758 514 10 or 9
2048 1459 1059 11 or 10
4096 3137 2338 12
8192 6023 4062 13 or 12
16384 12414 8459 13 or 14
32768 22620 15812 14
65536 54179 30213 16
found 2421 items in 4800 searches (50%).
...press enter...
Return to
Outline page
/
assignment description