# Searching a Young tableau

An $n \times n$ Young tableau is an $n \times n$ matrix of distinct integers, with each row and each column sorted in increasing order.

Now, we are given an $n \times n$ Young tableau $T$ and an integer $x$ which is known to appear in $T$. The goal is to find $x$ in $T$. That is, find $1\leq i,j \leq n$ such that $T_{ij}=x$. In order to do so, only comparisons are allowed. The result of a comparison is one of $\leq,\geq,=$. Comparisons are allowed between elements of $T$ or between $x$ and an element of $T$.

How many comparisons are needed in the worst case to find $x$ (asymptotically)?

Obviously, you can't do better than $O(\log n)$ comparisons because each comparison gives $O(1)$ bits of information, while there are $O(\log n)$ bits of information in the pair $i,j$.

On the other hand, the best algorithm I could think of to find $x$ uses $O(n)$ comparisons. It works as follows:

1. $i \leftarrow 1, j \leftarrow n$
2. While $T_{ij} \neq x$:
a. If $T_{ij} < x$ Then $i \leftarrow i+1$
b. If $T_{ij} > x$ Then $j \leftarrow j-1$
3. Return $i,j$

In each iteration we rule out either a row or a column, so we are done after $O(n)$ comparisons.

Can we close the gap between $O(\log n)$ and $O(n)$?

-

## 1 Answer

It is clearly not possible to do better then $O(n)$. Even if I give you the additional information that the smallest $\binom n2$ entries fill the upper-left triangle of that size and the largest $\binom n2$ entries similarly fill the bottom-right triangle, that leaves the diagonal given by $i+j=n+1$ for the remaining $n$ entries, and they could be positioned according to any permutation of $n$. If $x$ is one of those $n$ entries the problem then comes down to finding $x$ in an unsorted array of length $n$, and this obviously cannot be done in less thatn $O(n)$ comparisons (you just need to stumble upon $x$).

-
Thank you very much. I posted a follow-up question: math.stackexchange.com/questions/294043/… – user3533 Feb 3 '13 at 23:13