A tight lower bound for searching a sorted array.

Arne Andersson, Johan Hstad, Ola Petersson

Browse the full STOC paper archive.