Suppose P_n={1,2,…,n} is a partially ordered set with the partial order defined by divisibility, that is, for any two elements i,j∈P_n satisfying i divides j, we have [Formula: see text] . A table A_n={a_i|i=1,2,…,n} of real numbers is said to be consistent with P_n, provided that for any two elements i,j∈{1,2,…,n} satisfying i divides j, a_i≤a_j. Given a real number x, we want to determine whether x∈A_n, by comparing x with as few entries of A_n as possible. In this paper, we investigate the complexity τ(n), measured by the number of comparisons, of the above search problem. We present a 55n72+O(ln²n) search algorithm for A_n and prove a lower bound (34+172160)n+O(1) on τ(n) using an adversary argument.