Revisit: 2D Array Sorted Along X and Y Axis

So, this is a common interview question. There's already a topic up, which I have read, but it's dead, and no answer was ever accepted. On top of that, my interests lie in a slightly more constrained form of the question, with a couple practical applications.

Given a two dimensional array such that:

• Elements are unique.
• Elements are sorted along the x-axis and the y-axis.
• Neither sort predominates, so neither sort is a secondary sorting parameter.
• As a result, the diagonal is also sorted.
• All of the sorts can be thought of as moving in the same direction. That is to say that they are all ascending, or that they are all descending.
• Technically,开发者_JAVA技巧 I think as long as you have a >/=/< comparator, any total ordering should work.
• Elements are numeric types, with a single-cycle comparator.
• Thus, memory operations are the dominating factor in a big-O analysis.

How do you find an element? Only worst case analysis matters.

Solutions I am aware of:

A variety of approaches that are:

O(nlog(n)), where you approach each row separately.

O(nlog(n)) with strong best and average performance.

One that is O(n+m):

Start in a non-extreme corner, which we will assume is the bottom right.

Let the target be J. Cur Pos is M.

If M is greater than J, move left.

If M is less than J, move up.

If you can do neither, you are done, and J is not present.

If M is equal to J, you are done.

Originally found elsewhere, most recently stolen from here.

And I believe I've seen one with a worst-case O(n+m) but a optimal case of nearly O(log(n)).

What I am curious about:

Right now, I have proved to my satisfaction that naive partitioning attack always devolves to nlog(n). Partitioning attacks in general appear to have a optimal worst-case of O(n+m), and most do not terminate early in cases of absence. I was also wondering, as a result, if an interpolation probe might not be better than a binary probe, and thus it occurred to me that one might think of this as a set intersection problem with a weak interaction between sets. My mind cast immediately towards Baeza-Yates intersection, but I haven't had time to draft an adaptation of that approach. However, given my suspicions that optimality of a O(N+M) worst case is provable, I thought I'd just go ahead and ask here, to see if anyone could bash together a counter-argument, or pull together a recurrence relation for interpolation search.

Here's a proof that it has to be at least Omega(min(n,m)). Let n >= m. Then consider the matrix which has all 0s at (i,j) where i+j < m, all 2s where i+j >= m, except for a single (i,j) with i+j = m which has a 1. This is a valid input matrix, and there are m possible placements for the 1. No query into the array (other than the actual location of the 1) can distinguish among those m possible placements. So you'll have to check all m locations in the worst case, and at least m/2 expected locations for any randomized algorithm.

One of your assumptions was that matrix elements have to be unique, and I didn't do that. It is easy to fix, however, because you just pick a big number X=n*m, replace all 0s with unique numbers less than X, all 2s with unique numbers greater than X, and 1 with X.

And because it is also Omega(lg n) (counting argument), it is Omega(m + lg n) where n>=m.

An optimal O(m+n) solution is to start at the top-left corner, that has minimal value. Move diagonally downwards to the right until you hit an element whose value >= value of the given element. If the element's value is equal to that of the given element, return found as true.

Otherwise, from here we can proceed in two ways.

Strategy 1:

1. Move up in the column and search for the given element until we reach the end. If found, return found as true
2. Move left in the row and search for the given element until we reach the end. If found, return found as true
3. return found as false

Strategy 2: Let i denote the row index and j denote the column index of the diagonal element we have stopped at. (Here, we have i = j, BTW). Let k = 1.

• Repeat the below steps until i-k >= 0
  1. Search if a[i-k][j] is equal to the given element. if yes, return found as true.
  2. Search if a[i][j-k] is equal to the given element. if yes, return found as true.
  3. Increment k

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11