You wouldn't need to do a binary search. The values are already MD5 hashes. You could do a hash table lookup in just a few CPU cycles since computing the hash is free.
Good point, though at a minimum you need to touch main memory twice which is 200+ clock cycles. And in practice that O(1) has an much worse constant factor.