We study the exact complexity of searching for a given element in a rigid data structure (i.e., an implicit data structure consistent with a fixed family of partial orders). In particular, we show how the ordering information available in the structure facilitates the search operation. Some general lower bounds on the search complexity are presented, which apply to concrete rigid data structures as well. Optimal search algorithms for certain rigid structures are also developed. Moreover, we consider a general problem of searching for a number of elements in a given set. Non-trivial lower bounds are derived and efficient search algorithms are constructed.