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