A Young Tableau is a 2D matrix A of dimensions M*N such that:

i,j in [0,M)x[0,N):

• for each p in (i,M), A[i,j] <= A[p,j]
• for each q in (j,N), A[i,j] <= A[i,q]

That is, it's sorted row-wise and column-wise. Since it may contain less than M*N numbers, the bottom-right values might be represented either as missing or using (in algorithm theory) infinity to denote their absence.

Now the (elementary) question: how to check if a given number is contained in the Young Tableau ?

Well, it's trivial to produce an algorithm in O(M*N) time of course, but what's interesting is that it is very easy to provide an algorithm in O(M+N) time:

Bottom-Left search:

1. Let x be the number we look for, initialize i,j as M-1, 0 (bottom left corner)
2. If x == A[i,j], return true
3. If x < A[i,j], then if i is 0, return false else decrement i and go to 2.
4. Else, if j is N-1, return false else increment j

This algorithm does not make more than M+N moves. The correctness is left as an exercise.

It is possible though to obtain a better asymptotic runtime.

Pivot Search:

1. Let x be the number we look for, initialize i,j as floor(M/2), floor(N/2)
2. If x == A[i,j], return true
3. If x < A[i,j], search (recursively) in A[0:i-1, 0:j-1], A[i:M-1, 0:j-1] and A[0:i-1, j:N-1]
4. Else search (recursively) in A[i+1:M-1, 0:j], A[i+1:M-1, j+1:N-1] and A[0:i, j+1:N-1]

This algorithm proceed by discarding one of the 4 quadrants at each iteration and running recursively on the 3 left (divide and conquer), the master theorem yields a complexity of O((N+M)**(log 3 / log 4)) which is better asymptotically.

However, this is only a big-O estimation...

So, here are the questions:

1. Do you know (or can think of) an algorithm with a better asymptotical runtime ?
2. Like introsort prove, sometimes it's worth switching algorithms depending on the input size or input topology... do you think it would be possible here ?

For 2., I am notably thinking that for small size inputs, the bottom-left search should be faster because of its O(1) space requirement / lower constant term.