#!/usr/bin/perl
use strict;
use warnings;

use Benchmark qw/cmpthese/;

my @ids=(int(rand(10)));
push(@ids,$ids[-1]+int(rand(10))) while(@ids<10000);
my $id=$ids[int(rand(scalar(@ids)))];

cmpthese (-1,
   {
       'docsnyder' => sub { binSearch(\@ids, $id, 0, $#ids) },
       'ToPeG' => sub { tpgSearch(\@ids, $id, 0, $#ids) },
   }
);




sub binSearch {
  my($arrRef, $val, $minIdx, $maxIdx) = @_;
  my($mid) = int(($maxIdx + $minIdx)/ 2);
  my($idx);

  return(($arrRef->[$mid] == $val) ? $mid : (($minIdx == $maxIdx) ? undef : (($arrRef->[$mid] >= $val) ? binSearch($arrRef, $val, $minIdx, $mid) : binSearch($arrRef, $val, $mid+1, $maxIdx))));
}

sub tpgSearch
{
  my ($ref, $val, $min, $max) = @_;
  if($id>=$$ref[$min] && $id<=$$ref[$max])
  {
   my $diff=($ids[$max]-$ids[$min])/($max-$min);
   my $pos=int($val/$diff);

   if($$ref[$pos]<$val)
   { $pos++ while($val>$$ref[$pos]); }
   elsif($$ref[$pos]>$val)
   { $pos-- while($id<$$ref[$pos]); }

   return $pos if($val==$$ref[$pos]);
  }
  return undef;
}