Understanding staircase search algorithm

The strategy from the earlier example could be used to create an algorithm. To explain this algorithm, we will use a 2D matrix sorted by row and column in ascending order and search for a target number. For the algorithm to work, the input matrix should meet the condition below.

• The matrix should be sorted in rows and columns, meaning each row and each column is sorted in ascending order.

If the condition is violated, the algorithm may fail to locate the target element. This can be seen in the example below, where the input does not satisfy the required sorting conditions.

Algorithm

The staircase search algorithm searches for a target value in a 2D matrix with N rows and M columns where each row and each column is sorted in ascending order. It exploits the sorted property of the matrix by starting at the top-right corner (a corner where one direction leads to strictly smaller values and the other to strictly larger ones) and moving only in directions that eliminate impossible positions, achieving efficient linear-time search. The algorithm begins by initializing two indices that define the current search range in which the target value may exist.

• `row = 0` - (first row)
• `col = M - 1` - (last column)