use strict;
use warnings;
use Data::Dumper;
use Benchmark qw(cmpthese);

my @ids = (0..10000);
my $id  = 10000;

Benchmark::cmpthese(-1,{
   'docSearch' => sub { docSearch(\@ids, $id, 0, $#ids) },
   'tpgSearch' => sub { tpgSearch(\@ids, $id, 0, $#ids) },
   'tunSearch' => sub { tunSearch(\@ids, $id, 0, $#ids) },
});

sub tunSearch {
   my ($arrRef, $val, $minIdx, $maxIdx) = @_;
   my $mid;

   while ($minIdx != $maxIdx) {
      $mid = int(($maxIdx + $minIdx)/ 2);
      if ($arrRef->[$mid] == $val) {
         return $mid;
      } elsif ($arrRef->[$mid] > $val) {
         #? docSearch($arrRef, $val, $minIdx, $mid)
         $maxIdx = $mid
      } else {
         #: docSearch($arrRef, $val, $mid+1, $maxIdx);
         $minIdx = $mid+1;
      }
   }

   return undef;
}

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

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

sub tpgSearch {
   my ($ref, $val, $min, $max) = @_;

   if($id >= $$ref[$min] && $id <= $$ref[$max]) {
      my $diff = ($ref->[$max] - $ref->[$min]) / ($max - $min);
      my $pos = int($val / $diff);

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

      return $pos if $val == $$ref[$pos];
   }

   return undef;
}