Or you can use binary search with slightly off-center binary or quaternary (four-way) searches to provide more consistent lookup times:

http://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-patholo...