Finding perfect matchings with as few database queries as possible
A $O(n \log n)$ solution works as follows:

For each man $M$, we find the matching woman in $O(\log n)$ queries. We start by dividing the women into two sets of size $n/2$. Using one query, we can find out which of the two halves contains $M$'s match. We recurse on that half.