Locating a value in a row- and column-sorted grid

An $m\times n$ matrix has every row sorted increasing from left to right and every column sorted increasing from top to bottom. How do you search it for a given value, and what is the cost?

Start at the top-right corner: $O(m+n)$. If the entry equals the target you are done; if it is larger, move left (everything below in that column is larger too); if smaller, move down (everything left in that row is smaller). Each step discards a whole row or column, so at most $m+n-1$ steps are needed.