Binary search reduces the search space exponentially as it proceeds, so actually quite a lot of the total comparisons can hit L1d cache. (Maybe half of them for a ~250GB dataset.)

Of course, you could keep a cacheable partial index of your huge dataset to accelerate the early part of your search as well.

Sounds like we're just reinventing B-trees.

Yep. I considered phrasing my answer that way.