You can read the entire file in and since the records are sorted you can do a simple binary search using bsearch() to speed up your search.