Howdy Paraxial, welcome to the Monastery!

Binary Searches on Sorted Text Files has a useful snippet of code for binary-searching text files. It's intended for sorted in its current state, but all you'd really need to do to adapt it to your needs is modify the conditions for the recursive calls. In fact, I'd pass a callback function there as an extra parameter instead of hardcoding anything specific.

One of the comments on that node also points out File::SortedSeek, which looks like it may well be useful.