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

[download]

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)

In reply to Re^4: Modified Binary Search by jethro
in thread Modified Binary Search by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • 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:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.