http://www.perlmonks.org?node_id=817414


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)