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 20261025.
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.
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 18 5
64 64 33 6
128 128 63 7
256 256 128 8
512 512 245 9
1024 1024 511 10
2048 2048 981 11
4096 4096 2217 12
8192 8192 4241 13
16384 16384 7489 14
32768 32768 18309 15
65536 65536 30725 16
found 0 items in 4800 searches (0%).
...press enter...
Comparison Counts for Successful Search
---------------------------------------
Length Unsorted Sorted Binary
------ -------- ------ ------
2 1 1 2
4 3 3 2
8 4 5 3
16 9 8 3
32 16 18 4
64 30 34 5
128 56 70 6
256 129 119 7
512 243 257 8
1024 502 538 9
2048 993 1221 10
4096 1861 2267 11
8192 4009 4070 12
16384 8641 8354 13
32768 16329 14691 14
65536 32794 35180 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 12 9 4
32 24 17 5
64 48 35 6
128 91 70 7
256 186 122 7
512 383 248 8
1024 735 518 9
2048 1565 1018 11
4096 3088 2023 11
8192 6079 4050 12
16384 12102 7947 14
32768 25605 15709 14
65536 45206 32110 16
found 2571 items in 4800 searches (54%).
...press enter...
Return to
Outline page
/
assignment description