Monotone matrix
= Monotone matrix
{title2=$a_{i,j}\leq a_{i+1,j},\quad a_{i,j}\leq a_{i,j+1}$}
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.