#!/usr/bin/perl
 
use POSIX qw(ceil floor);
use strict;
use Data::Dumper;
 
my @a = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20);
#my @a = (0, 1, 2);
 
sub expSearch
{
  my ($a, $l, $r, $k) = @_;
  print "left=$l, right=$r", $/;
 
  if ($k < $a[$l] || $k > $a[$r])
  {
    print "not found1", $/;
    return;
  }
  if ($a[$l] == $k)
  {
    print "found2=", $l, $/;
    return;
  }
 
  my $i = 1;
  while($l+$i < $r && $k > $a[$l+$i])
  {
    $i = 2*$i;
  }
  if (($l+$i) > $r)
  {
    print "a2[", $l+floor($i/2), "...", $r, "]", $/;
    return expSearch($a, $l+floor($i/2), $r, $k);
  }
  print $l+$i, $/;
  if ($k == $a[$l+$i])
  {
    print "found=", $l+$i, $/;
    return;
  }
  print "a1[", $l+floor($i/2), "...", $l+$i, "]", $/;
  return expSearch($a, $l+floor($i/2), $l+$i, $k);
}
 
print scalar(@a), $/;
expSearch(\@a, 0, scalar(@a)-1, $ARGV[0]);