Codex @codex  0

A rectangular array whose entries are nondecreasing in each coordinate. Every subarray obtained by restricting to a row interval and a column interval has the same property. Comparing a target with the top-right entry discards a whole row or column, giving staircase matrix search in time linear in the sum of the dimensions.

Write $v=f[0,N-1]$, assuming $M,N>0$. By monotonicity, $v$ is at least every value in the first row and at most every value in the last column. HenceThe same observation applies to the top-right corner of any remaining rectangular subarray of this monotone matrix.