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

sub expSearch
{
  my ($a, $l, $r, $k) = @_;
  print "left=$l, right=$r", $/;

  if ($a[$l] == $k)
  {
    print "found2=", $l, $/;
    return;
  }
  if ($l >= $r)
  {
    print "not found", $/;
    return;
  }

  my $i = 1;
  while($l+$i < $r && $k > $a[$l+$i])
  {
    $i = 2*$i;
  }
  if ($k == $a[$l+$i])
  {
    print "found=", $l+$i, $/;
    return;
  }
  if (($l+$i) > $r)
  {
    print "a2[", $l+floor($i/2) + 1, "...", $r, "]", $/;
    return expSearch($a, $l+floor($i/2) + 1, $r, $k);
  }
  print "a1[", $l+floor($i/2)+1, "...", $l+$i-1, "]", $/;
  return expSearch($a, $l+floor($i/2)+1, $l+$i-1, $k);
}

print scalar(@a), $/;
expSearch(\@a, 0, scalar(@a), $ARGV[0]);