#!/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)/log(2));

for ('aa','ab','ce','dn','ea','fr','lb') {
    my ($beg,$iterations)= binary_search($_,@data);
    say "Found first '$_' at position $beg after $iterations iterations";
}

#----------------------

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