A large body of work studies the complexity of selecting the
$j$-th largest element in an arbitrary set of $n$ elements (a.k.a.
the select$(j)$ operation). In this work, we study the
complexity of select in data that is partially structured by
an initial preprocessing stage and in a data structure that
is dynamically maintained. We provide lower and upper
bounds in the comparison based model. For preprocessing, we show
that making at most $\alpha(n) \cdot n$ comparisons during
preprocessing (before the rank $j$ is provided) implies that select$(j)$ must make at least $(2 + \epsilon)({n}/{e 2^{\alpha(n)}})$ comparisons in the worst case, where $\epsilon > 2^{-40}$.

For dynamically maintained data structures, we show that if
the amortized number of comparisons executed with each insert operation is bounded by $i(n)$, then select$(j)$
must make at least $(2 + \epsilon)({n}/{e 2^{i(n)}})$ comparisons
in the worst case, no matter how costly the other data structure
operations are. When only insert is used, we provide a lower
bound on the complexity of findmedian. This lower bound is
much higher than the complexity of maintaining the minimum, thus
formalizing the intuitive difference between findmin and
findmedian.

Finally, we present a new explicit adversary for comparison based
algorithms and use it to show adversary lower bounds for selection
problems. We demonstrate the power of this adversary by improving
the best known lower bound for the findany operation in a
data structure and by slightly improving the best adversary lower
bound for sorting.