algorithm - Revisit: 2D Array Sorted Along X and Y Axis -

so, common interview question. there's topic up, have read, it's dead, , no answer ever accepted. on top of that, interests lie in more constrained form of question, couple practical applications.

given 2 dimensional array such that:

• elements unique.
• elements sorted along x-axis , y-axis.
• neither sort predominates, neither sort secondary sorting parameter.
• as result, diagonal sorted.
• all of sorts can thought of moving in same direction. ascending, or descending.
• technically, think long have >/=/< comparator, total ordering should work.
• elements numeric types, single-cycle comparator.
• thus, memory operations dominating factor in big-o analysis.

how find element? worst case analysis matters.

solutions aware of:
variety of approaches are:
o(nlog(n)), approach each row separately.
o(nlog(n)) strong best , average performance.

one o(n+m):
start in non-extreme corner, assume bottom right.
let target j. cur pos m.
if m greater j, move left.
if m less j, move up.
if can neither, done, , j not present.
if m equal j, done.
found elsewhere, stolen here.

and believe i've seen 1 worst-case o(n+m) optimal case of o(log(n)).

what curious about:

right now, have proved satisfaction naive partitioning attack devolves nlog(n). partitioning attacks in general appear have optimal worst-case of o(n+m), , not terminate in cases of absence. wondering, result, if interpolation probe might not better binary probe, , occurred me 1 might think of set intersection problem weak interaction between sets. mind cast towards baeza-yates intersection, haven't had time draft adaptation of approach. however, given suspicions optimality of o(n+m) worst case provable, thought i'd go ahead , ask here, see if bash counter-argument, or pull recurrence relation interpolation search.

here's proof has @ least omega(min(n,m)). let n >= m. consider matrix has 0s @ (i,j) i+j < m, 2s i+j >= m, except single (i,j) i+j = m has 1. valid input matrix, , there m possible placements 1. no query array (other actual location of 1) can distinguish among m possible placements. you'll have check m locations in worst case, , @ least m/2 expected locations randomized algorithm.

one of assumptions matrix elements have unique, , didn't that. easy fix, however, because pick big number x=n*m, replace 0s unique numbers less x, 2s unique numbers greater x, , 1 x.

and because omega(lg n) (counting argument), omega(m + lg n) n>=m.