You could have an array where subscript N indicates key N thousand, and the value of the array element would be the disk offset to look at.

Let's assume you have fixed length records of 30 bytes. Element 21 having value 999990 would mean the first key greater than or equal to 21,000 was stored at disk offset 999,990.

Having said all that, I'd also suggest using a binary search.