This question is a follow up on: Searching a Young tableau.
The previous question was "How many comparisons are needed to find an element $x$ in an $n \times n$ Young tableau of distinct elements (asymptotically)?".
The algorithm presented in the question itself shows an upper bound of $O(n)$ while the accepted answer gives a matching lower bound of $\Omega(n)$.
The reasoning behind the lower bound is essentially that even in the special case where the tableau is $-\infty$ above the diagonal and $+\infty$ below the diagonal, and even if this this extra information is given to the inquirer, the elements on the diagonal can be ordered arbitrarily and thus the problem is at least as hard as finding an element in an unsorted array of $n$ elements.
Now, to an enhanced version of this question:
Given an $n \times n$ Young tableau of distinct elements and list of $n$ distinct elements $x_1,\dotsc,x_n$ which are all known to appear in the table. What is the smallest number of comparisons needed to find all $n$ elements in the table?
The allowed types of comparsions are between elements in the list, between elements in the table, and between and element in the list and an element in the table.
Searching for the elements in the list one-by-one requires $O(n^2)$ comparisons. Yet, the previous lower bound does not generalize to give an $\Omega(n^2)$ bound because matching between two unsorted lists of $n$ elements each may be done in $\Theta(n\log n)$ time by sorting both lists.