[Java] Find value in sorted matrix

Given a NxM matrix (where M could be equal to N) which is sorted by rows and colums, find whether a value is in the matrix.

The sort property ensures that for a given row or columns, all values are in ascending order. It is not guaranteed, that the first value of each row or column is greater than the last value of the previous row or column, for example:

10, 20, 30, 40
15, 25, 35, 45
27, 29, 37, 48
32, 33, 39, 50

is a sorted matrix.

Knowing the matrix is sorted, we can start from any corner and determine where might our value be within the current row and column boundary values. We can then discard entire rows and columns while moving towards the potential location of our value.

For example searching for value 21 and starting from top right corner, we have two possible ranges: 10-40 for the row and 40-50 for the column.

21 fits within the row range, therefore we can discard the whole column and move to the previous one.

New range is 10-30 for row and 30-39 for column. Again we fit in row range and move to previous column.

New range is 10-20 for row and 20-25 for column. Now we fit in column range, therefore we move to next row.

New range is 15-25 for row and 25-33 for column. We fit in row range, move to previous column.

New range is 15 only for row and 15-32 for column. Move to next row.

Last range is 27 only for row and 27-32 for column. Our value doesn't fit in either range, therefore is not in the matrix.

Note that for a 16 element square matrix we only moved over 7 values, since at every iteration we discard a full row or column, in the worst case we do O(N+M) work where we walk down a whole column and then backwards over a whole row.

This is also useful for other similar search problems where the matrix has a sorted property, for example:

Given a sorted boolean matrix, find the row that has the highest number of "true" values. Example

F, F, T, T
F, F, F, F
F, F, F, T
T, T, T, T

While in the previous exercise we could start from any corner, in this case only starting from the top or bottom right will lead to the O(M+N) solution (worst case is a matrix that contains only "false" values).

Reasoning is this: if we find a "true" value at the end of a row, we keep walking back until we either reach the beginning of the row (and find the maximum allowed solution) or a "false". When we find a false, the current best is row length - index of false + 1

Now a better result must lay on the left side of this position in the next rows, otherwise it wouldn't be a longer sequence of "true" values as each row is sorted. We can therefore move to subsequent rows and repeat this logic.

You can check my implementation of findValueInSortedMatrix on my Gist along with some tests in FindValueInSortedMatrixJTests.