A. Andersson, T. Hagerup, J. Håstad, and O. Petersson. The complexity of searching a sorted array of strings.
In Proc. 26th ACM Symposium on Theory of Computing, pages 317--325. ACM Press, 1994.

(Mathematical expressions are simplified in this html-dokument. They should be readable enough to get the flavour.)

We present an algorithm for finding a given k-character string in an array of n strings, arranged in alphabetical order, using

O( k loglog n / loglog (4+k loglog n / log n)
+ k + log n)

character comparisons. This improves significantly upon previous bounds.

Full paper (postscript)
Full paper (pdf)