Tight Bounds for Searching a Sorted Array of Strings
Arne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson · SIAM Journal on Computing · 2000
Given a k-character query string and an array of n strings arranged in lexicographical order, computing the rank of the query string among the n strings or deciding whether it occurs in the array requires the inspection of $$ \Theta\left( \frac {k\log {\log n}} {\log {\log {(4+\frac{k \log{\log n}}{\log n})}}}+k+\log n\right) $$ characters in the worst case.