A 4MB file is not really very big, and 10 seconds is a long time. Here is an example program which creates a 4MB file with 100000 lines, and then searches the file linearly for a line by id. It finishes the search in well under 10 seconds, without any special trickery. I don't believe you need an "optimal algorithm" to meet your stated specifications. Even the standard Un*x tool grep can find a specified line in a file that big in less than 4/100ths of a second.

You might want to research about premature+optimization, Premature optimization

#!/usr/bin/perl

use strict;
use warnings;

# make a 4MB file, 100000 lines == 40bytes/line
print("creating file...\n");
create_file("testfile.txt", 40, 100000);

# find a line in the file
print("searching file...\n");
find_line("testfile.txt", "000099000");
print("searching file...\n");
find_line("testfile.txt", "000000100");
print("searching file...\n");
find_line("testfile.txt", "000099999");

sub create_file
{
    my $filename = shift;
    my $bytes = shift;
    my $lines = shift;

    my @chars = map{chr($_)} (32..126);
    open FILE, ">$filename" or die "can't open $filename: $!";
    for (my $i = 0; $i < $lines; $i++)
    {
        # make id, 10 bytes
        my $line = sprintf("%09d ", $i);
        # make rest of line
        for (my $j = 0; $j < $bytes-10; $j++)
        {
            $line .= $chars[rand(@chars)];
        }
        print FILE "$line\n";
    }
    close FILE or die "can't close $filename: $!";
}

sub find_line
{
    my $filename = shift;
    my $id = shift;

    my $start = time;
    open FILE, "<$filename" or die "can't open $filename: $!";
    while (my $line = <FILE>)
    {
        if ($line =~ m/^$id/)
        {
            print "FOUND! $line";
            last;
        }
    }
    my $end = time;
    my $time_taken = $end - $start;
    if ($time_taken < 10)
    {
        print "Finished in $time_taken seconds. ",
            "That's less than 10 seconds -- mission accomplished!\n";
    }
}

__END__
Output:

creating file...
searching file...
FOUND! 000099000 H_eHMl}XjMhkQysu1h?ON8y1d9loP=
Finished in 1 seconds. That's less than 10 seconds -- mission accompli
+shed!
searching file...
FOUND! 000000100 w6M:YgK1{*AmG;Lh5Cp,unCo\[aJQ`
Finished in 0 seconds. That's less than 10 seconds -- mission accompli
+shed!
searching file...
FOUND! 000099999 u#656~vOL^HMy{V_[D]@-2e}tH}Auo
Finished in 0 seconds. That's less than 10 seconds -- mission accompli
+shed!
[download]