If you had to check each number between 1 and a trillion, one by one, your worse case would be a trillion guesses, and average would be 500 billion, but with the binary search's divide and conquer approach, that problem domain a trillion members big is reduced to 40 guesses.
Although I perfectly understand what you really mean (and agree with everything else that you said), the statement above about the average search is technically not true if you play according to the rules of the game, i.e. if you select a number within the range previously determined by the previous tries: the average would be much much smaller than what you said. As an example, let me take the trillion (1e12) case.
The following program is just selecting a wild guess within the admitted range and adjusting the range in accordance with the results of the previous try.
Now running the program a few times:use strict; use warnings; my ($low, $high) = qw /0 1e12/; my $search_number = int rand $high; my $guess; my $count = 0; while (1) { $guess = $low + int rand ($high - $low); last if $guess == $search_number; if ($search_number > $guess) { $low = $guess; } else { $high = $guess; } printf "%12d", $guess; print " - Range is $low - $high \n"; $count++; } print "Searched value is : $guess, found in $count tries \n";In brief, 45, 37 and 50 tries. This is far from being bad. Compared with the optimal 40 guesses, the random approach is actually fairly good.$ perl number_guess.pl 383169808282 - Range is 0 - 383169808282 284389450338 - Range is 0 - 284389450338 31362751649 - Range is 0 - 31362751649 17265066286 - Range is 17265066286 - 31362751649 22982580226 - Range is 22982580226 - 31362751649 26509192840 - Range is 22982580226 - 26509192840 23581338963 - Range is 23581338963 - 26509192840 23956176067 - Range is 23956176067 - 26509192840 24944698798 - Range is 24944698798 - 26509192840 26246852405 - Range is 24944698798 - 26246852405 26224060754 - Range is 24944698798 - 26224060754 26155406210 - Range is 24944698798 - 26155406210 24985188326 - Range is 24985188326 - 26155406210 25110319199 - Range is 25110319199 - 26155406210 26032170822 - Range is 25110319199 - 26032170822 25969913969 - Range is 25110319199 - 25969913969 25285144016 - Range is 25110319199 - 25285144016 25126279555 - Range is 25126279555 - 25285144016 25266882116 - Range is 25126279555 - 25266882116 25212737880 - Range is 25126279555 - 25212737880 25148145727 - Range is 25126279555 - 25148145727 25128957708 - Range is 25126279555 - 25128957708 25126823028 - Range is 25126823028 - 25128957708 25127517039 - Range is 25127517039 - 25128957708 25128531225 - Range is 25127517039 - 25128531225 25128131740 - Range is 25127517039 - 25128131740 25127788667 - Range is 25127788667 - 25128131740 25128066658 - Range is 25127788667 - 25128066658 25127866373 - Range is 25127866373 - 25128066658 25127958852 - Range is 25127958852 - 25128066658 25128031930 - Range is 25127958852 - 25128031930 25127992718 - Range is 25127958852 - 25127992718 25127963745 - Range is 25127958852 - 25127963745 25127958886 - Range is 25127958886 - 25127963745 25127963134 - Range is 25127963134 - 25127963745 25127963526 - Range is 25127963526 - 25127963745 25127963629 - Range is 25127963629 - 25127963745 25127963642 - Range is 25127963642 - 25127963745 25127963723 - Range is 25127963642 - 25127963723 25127963682 - Range is 25127963682 - 25127963723 25127963716 - Range is 25127963682 - 25127963716 25127963715 - Range is 25127963682 - 25127963715 25127963699 - Range is 25127963699 - 25127963715 25127963706 - Range is 25127963699 - 25127963706 25127963700 - Range is 25127963700 - 25127963706 Searched value is : 25127963702, found in 45 tries $ perl number_guess.pl 304648251130 - Range is 0 - 304648251130 223751316634 - Range is 0 - 223751316634 95867635411 - Range is 0 - 95867635411 88940918193 - Range is 0 - 88940918193 4052880182 - Range is 4052880182 - 88940918193 41049022846 - Range is 41049022846 - 88940918193 70221320933 - Range is 70221320933 - 88940918193 76852100855 - Range is 70221320933 - 76852100855 71514664707 - Range is 70221320933 - 71514664707 70897850480 - Range is 70221320933 - 70897850480 70891457527 - Range is 70221320933 - 70891457527 70464394115 - Range is 70221320933 - 70464394115 70391209051 - Range is 70221320933 - 70391209051 70376508106 - Range is 70376508106 - 70391209051 70386803120 - Range is 70376508106 - 70386803120 70377744895 - Range is 70377744895 - 70386803120 70379549079 - Range is 70379549079 - 70386803120 70384053253 - Range is 70379549079 - 70384053253 70380716744 - Range is 70380716744 - 70384053253 70380996210 - Range is 70380996210 - 70384053253 70381552052 - Range is 70381552052 - 70384053253 70382155219 - Range is 70381552052 - 70382155219 70381905458 - Range is 70381552052 - 70381905458 70381852884 - Range is 70381852884 - 70381905458 70381870009 - Range is 70381852884 - 70381870009 70381863427 - Range is 70381852884 - 70381863427 70381858823 - Range is 70381858823 - 70381863427 70381862491 - Range is 70381858823 - 70381862491 70381859161 - Range is 70381858823 - 70381859161 70381859072 - Range is 70381858823 - 70381859072 70381858911 - Range is 70381858911 - 70381859072 70381859023 - Range is 70381858911 - 70381859023 70381858955 - Range is 70381858911 - 70381858955 70381858931 - Range is 70381858911 - 70381858931 70381858929 - Range is 70381858911 - 70381858929 70381858926 - Range is 70381858911 - 70381858926 70381858918 - Range is 70381858918 - 70381858926 Searched value is : 70381858925, found in 37 tries $ perl number_guess.pl 905377320337 - Range is 0 - 905377320337 845955622764 - Range is 845955622764 - 905377320337 855434070342 - Range is 855434070342 - 905377320337 859908637620 - Range is 859908637620 - 905377320337 885242097183 - Range is 859908637620 - 885242097183 870013176596 - Range is 870013176596 - 885242097183 880006044551 - Range is 870013176596 - 880006044551 879259589401 - Range is 870013176596 - 879259589401 870604247325 - Range is 870604247325 - 879259589401 876279837683 - Range is 876279837683 - 879259589401 878643948457 - Range is 878643948457 - 879259589401 878866887884 - Range is 878866887884 - 879259589401 879157201665 - Range is 878866887884 - 879157201665 879102660515 - Range is 879102660515 - 879157201665 879149825206 - Range is 879102660515 - 879149825206 879136864479 - Range is 879136864479 - 879149825206 879145707273 - Range is 879136864479 - 879145707273 879142710248 - Range is 879142710248 - 879145707273 879144045425 - Range is 879144045425 - 879145707273 879145197289 - Range is 879144045425 - 879145197289 879144335588 - Range is 879144335588 - 879145197289 879144785783 - Range is 879144785783 - 879145197289 879145175141 - Range is 879144785783 - 879145175141 879145086879 - Range is 879144785783 - 879145086879 879144889416 - Range is 879144785783 - 879144889416 879144872138 - Range is 879144785783 - 879144872138 879144862882 - Range is 879144785783 - 879144862882 879144820219 - Range is 879144785783 - 879144820219 879144790488 - Range is 879144790488 - 879144820219 879144810577 - Range is 879144790488 - 879144810577 879144805489 - Range is 879144790488 - 879144805489 879144795167 - Range is 879144795167 - 879144805489 879144803065 - Range is 879144795167 - 879144803065 879144802583 - Range is 879144795167 - 879144802583 879144797806 - Range is 879144795167 - 879144797806 879144797348 - Range is 879144795167 - 879144797348 879144796645 - Range is 879144796645 - 879144797348 879144796700 - Range is 879144796700 - 879144797348 879144797228 - Range is 879144796700 - 879144797228 879144796800 - Range is 879144796800 - 879144797228 879144797146 - Range is 879144797146 - 879144797228 879144797219 - Range is 879144797146 - 879144797219 879144797180 - Range is 879144797146 - 879144797180 879144797169 - Range is 879144797169 - 879144797180 879144797178 - Range is 879144797169 - 879144797178 879144797174 - Range is 879144797174 - 879144797178 879144797176 - Range is 879144797174 - 879144797176 879144797174 - Range is 879144797174 - 879144797176 879144797174 - Range is 879144797174 - 879144797176 879144797174 - Range is 879144797174 - 879144797176 Searched value is : 879144797175, found in 50 tries $
In reply to Re^2: Updates to a guessing number script by Laurent_R
in thread Updates to a guessing number script by Anonymous Monk
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data! Titles consisting of a single word are discouraged, and in most cases are disallowed outright. Read Where should I post X? if you're not absolutely sure you're posting in the right place. Please read these before you post! — Posts may use any of the Perl Monks Approved HTML tags:
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
For: Use: & & < < > > [ [ ] ] Link using PerlMonks shortcuts! What shortcuts can I use for linking? See Writeup Formatting Tips and other pages linked from there for more info.