On my computer, it takes about 2 seconds to run on an array with 1 million ints:

my @arr = (1 .. 1_000_000);
my $x   = 425983;
printf "search for $x? found at position: %s\n", binarySearch(0,$x,\@a
+rr);
[download]

However, if I go to 5 million, my operating system starts thrashing. Maybe that's what's happening to you too (memory usage starts becoming an issue). It's also quite possible that python has lower overhead for integer scalars than Perl, but I have no idea.

One thing I noticed is that you pass in the array by reference (good idea), but the first thing you do is copy it entirely into a local variable. Why not keep accessing it by reference, like this: (I changed some other things around too)

sub binarySearch {
  my ($begin, $query, $array) = @_;

  return 0        if $query < $array->[0]        and $begin == 1;
  return $#$array if $query > $array->[$#$array] and $begin == 0;

  my ($left,$right,$prevCenter, $center) = (0, $#$array, -1);

  while(1) {
    $center = int (($left + $right)/2);

    if ($query == $array->[$center]) {
      if ($begin == 1)  {
        $center-- until $center == 0
                     or $array->[$center] != $array->[$center-1];
      } else {
        $center++ until $center == $#$array
                     or $array->[$center] != $array[$center+1];
      }
      return $center;
    }

    if ($center == $prevCenter) {
      return $right   if $begin == 1;
      return $right-1 if $begin == 0;
    }
    $right = $center if $query < $array->[$center];
    $left  = $center if $query > $array->[$center];
    $prevCenter = $center;
  }
}
[download]

This should save a lot of memory. It now takes about 10 seconds running on 5 million ints for me.