The complexity of the search problem for a very broad class of data structures is estimated. The lower (Information Theoretic) bound and the upper bound differ by a small multiplicative constant.
['Nathan Linial', 'Michael E. Saks']
Information bounds are good for search problems on ordered data structures