Sorry for the delay in the post.

The trick to the index is it must be a sorted index (suggested ascii sorted). So if I have 10 numbers I would make an index that lookes like this

001 005
020 006
030 001
031 007
050 009
060 002
070 003
080 010
090 004
100 008
[download]

Pretty boring. Notice that it is fixed width. In this example the first column is the sorted index, the second column is the real row number that the data would be in the main file.

The following is the basic code I would use to search the given index file. It would do the following:
1. Seek to and read in 060
2. Not found max set to beginning of 060
3. Seek to and read in 030
4. Not found max set to beginning of 030
5. Seek to and read in 020
6. Found spit out the result.

my $search = sprintf("%03d",20); # pad the search thingy
my $ind_length = 3;    # length of sorted index column
my $line_length = 8;   # line length
my $size = (-s $file);
die "Corrupt file" unless $size % $line_length == 0;
open(IND,$file) || die $!;  # get the file ready
my $min = 0;        # lower bound
my $max = $size;    # upper bound

my $result = undef;
my $match;
while(1){
  my $pos = $ind_length * int(
       ($min/$ind_length + $max/$ind_length) / 2
         ); # find the middle (make sure it is at the
            # beginning of a row
  last if $pos == $min;   # there is no result
  seek(IND,$pos,0);       # go to the middle
  sysread(IND,$match,$ind_length); # read the info

  # found it!
  if( $match eq $search ){
    seek(IND,($pos+$ind_length+1),0);
    sysread(IND,$result,$ind_length); # read the real index
    last;
  }
  if( $match gt $search ){
    $max = $pos;
  }else{
    $min = $pos;
  }
}
if( defined $result ){
  print "Found it ($result)\n";
}
[download]