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;
}