Linear search algorithm in sorted table

When there is a need to find something in a sorted data sequence, a binary search that works in logarithmic time immediately comes to mind. But sometimes even time-tested solutions turn out to be outsiders, giving way to the “youth”.
Suppose we have an NxM table, the elements in which are sorted by rows and columns, for example, this:


You need to be able to quickly find the desired item in this table.

If we use a binary search on a column, going through all the rows and O (1) to decide whether to search for an element in a given row (or vice versa, to go through the columns and search by rows), we get the complexity of O (N * logM) operations. However, for this problem there is a more beautiful solution that works in O (N + M) time:

1. Starting in the lower left cell.
2. If the required element stands there, then the deed is done and “the Moor can leave.”
3. If the required element is greater than the current one, go one step to the right (then the entire column in which we are now is removed from consideration). If you have nowhere to go, it means that there is no element in the table.
4. If the required one is less than the current one, go upwards, removing the current line from consideration. Again, if there is nowhere to go, give up and say that the item was not found.
5. GOTO 2
')
The search will go, for example, like this:



It is easy to understand that the algorithm has a linear complexity, because at each step we get rid of either a row or a column, reducing one of the dimensions of the problem by one.

So sometimes it is useful to reinvent the wheel instead of using proven solutions :).

PS The task and the algorithm are taken from the A series of Programming Job Interview Challenge . There are many other interesting tasks there.