Lower bounds for predecessor searching in the cell probe model

Pranab Sen, S. Venkatesh

We consider a fundamental problem in data structures, static predecessor searching: Given a subset S of size n from the universe [m], store S so that queries of the form "What is t…