Assuming you are only searching on a small part of each record you could create a key file and store the keys and their offsets, much like is done in a database.

If not, then maybe you could keep a subset of keys, maybe 1 out of 100, then you could binary search to the key equal or less than the one you need and seek forward through the 100 records in between... kind of a reasonable trade-off.