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

in reply to Re^3: 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
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