Good point, though technically a hashtable can only test for existence and can't find the lower bound. Also, a hashtable is likely to require more memory.
A minimal perfect hashtable is memory optimal: BDZ/BPZ (1.95 bit per key)
http://cmph.sourceforge.net/ or https://github.com/rurban/nbperf