A binary search seems a good idea: have a look at: Search::Binary.

Update: Searching for 5000 "matches" in an array of 10000 headers took this program 3 seconds:

use Modern::Perl;

use Search::Binary;

#fake lists of headers and matches
my @headers = map {state $header; $header += int(rand(10)) + 1} (1 .. 
+10000);
my @matches = map {int(rand($headers[-1])+1)} (1 .. 5000);

my $min = 0;
my $max = @headers - 1;

my $read = sub {
    my ($handle, $val, $position) = @_;
    state $last_position;
    if ($position) {
        $last_position = $position;
        return $val <=> $headers[$position], $position;
    }
    else {
        $last_position++;
        return $val <=> $headers[$last_position], $last_position;
    }
};

my $start_time = time;
for my $match (@matches) {
    my $pos = binary_search($min, $max, $match, $read, undef, 10);
    $pos++ if $headers[$pos] == $match;
    say "$match is between $headers[$pos - 1] and $headers[$pos] (posi
+tion: $pos)";
}
say "That took me ", time - $start_time, " seconds.";
[download]