Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Re^4: Modified Binary Search

by jethro (Monsignor)
on Jan 14, 2010 at 14:42 UTC ( #817414=note: print w/replies, xml ) Need Help??


in reply to Re^3: Modified Binary Search
in thread Modified Binary Search

Ok, here is the proof. I programmed the algorithm as described in my first post:

#!/usr/bin/perl use 5.10.0; use strict; use warnings; use Data::Dumper; my @data; for ('aa'..'lz') { push @data, ($_) x 7; } my $size= scalar(@data); say 'array size is ',$size,', log2 of ',$size,' is ',int(log($size)/lo +g(2)); for ('aa','ab','ce','dn','ea','fr','lb') { my ($beg,$iterations)= binary_search($_,@data); say "Found first '$_' at position $beg after $iterations iteration +s"; } #---------------------- sub binary_search { my ($search,@data)= @_; return(0) if (@data<2); my $beg=0; my $end= @data-1; my $iter=0; while ($beg<$end-1) { my $middle= int(($end+$beg)/2); if ($data[$middle] lt $search) { $beg=$middle; } else { $end=$middle; } $iter++; } #handle the special case if you are looking for $data[0] return($beg,$iter) if ($data[$beg] eq $search); return($end,$iter); } #output: array size is 2184, log2 of 2184 is 11 Found first 'aa' at position 0 after 11 iterations Found first 'ab' at position 7 after 11 iterations Found first 'ce' at position 392 after 11 iterations Found first 'dn' at position 637 after 11 iterations Found first 'ea' at position 728 after 11 iterations Found first 'fr' at position 1029 after 11 iterations Found first 'lb' at position 2009 after 11 iterations

Ok, not a proof in formal language but good enough for us, I hope. As you can see it is a binary search, it takes exactly the number of iterations predicted to find the items. Also it is evident that it finds the first item (see the first two results, and also all following results are dividable by 7)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://817414]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (3)
As of 2021-06-14 06:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What does the "s" stand for in "perls"? (Whence perls)












    Results (60 votes). Check out past polls.

    Notices?