Also, there were a couple of bugs in my binary chop as I warned there might be. Anyway, this is a corrected and faster version. Run against a file that contains 20e6 values (from 5 .. 100e6 in steps of 5) randomly picking values approx. half of which should be misses, it achieves ~20,000 lookups / second:

#! perl -slw
use strict;
use Math::Random::MT qw[ rand ];
use Benchmark::Timer; my $T = new Benchmark::Timer;

open IN, '<:raw', '666269.bin' or die $!;
my $data; sysread IN, $data, -s( '666269.bin' ) or die $!;
close IN;

sub lookup {
    my $target = pack 'N', shift;
    my( $left, $right ) = ( 0, ( length( $data ) ) / 6 );
    while( $left < $right ) {
        my $mid = int( ( $left + $right ) / 2 );
        my $key = substr $data, $mid * 6, 4;
        if( $key lt $target ) {
            $left = $mid +1;
        }
        elsif( $key gt $target ) {
            $right = $mid;
        }
        elsif( $key eq $target ) {
            my( $key, $val ) = unpack 'NS', substr $data, $mid * 6, 6;
            return $val;
        }
    }
}

my $found = 0;
my $n = $ARGV[ 0 ] || 1000;
my $label = "Lookup $n values";
$T->start( $label );
for ( 1 .. $n ) {
    $found++ if lookup( 5*int( rand 19e6 ) + int( rand 2 ) );
}
$T->stop( $label );
$T->report;

print "found: $found";

__END__
C:\test>666269 1e6
1 trial of Lookup 1e6 values (53.287s total)

found: 500062
[download]

Maybe you need binmode?