A. Andersson, J. Håstad, and O. Petersson. A tight lower bound for searching a sorted array.
In Proc. 27th ACM Symposium on Theory of Computing, pages 417--426. ACM Press, 1995.

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

We show that given a $k$-character query string and an array of $n$ strings arranged in alphabetical order, finding a matching string or report that no such string exists requires

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

character comparisons in the worst case, which is tight.

Full paper (postscript)
Full paper (pdf)