Searching the space of permutations
Consider the following set of $n$ orders, which I give for $n = 6$:
$$
123456 \\
213456 \\
132456 \\
124356 \\
123546 \\
123465
$$
Hopefully the generalization to arbitrary $n$ is clear.

If you never compare $i$ and $i+1$ then you cannot tell apart permutation $1$ from permutation $i+1$. This means that you need at least $n-1$ comparisons (this is not an argument, but it can be converted to one); this is tight (for this example).

Let me also mention two well-known papers in the area:


Fredman showed that if there are $\Gamma$ many possible orderings, then you can find the correct one using $\log_2 \Gamma + 2n$ queries.
Kahn and Kim showed that if the potential orderings constitute all possible orderings extending some partial order, then $O(\log \Gamma)$ queries suffice.