If the target is larger/smaller than an element at the end of a row/column, what can you say about where the target is.

This solution usees recursion to elininate one line/column at every call. If the matrix NxM then the algorithm will run in O(N + M).


int searchMatrix(int target, int[][] matrix, i, j)
    int t = matrix[i][j];

    if (target == t)
       return t;
    else if (target > t)
       return searchMatrix(target, matrix, i + 1, j);
    else
       return searchMatrix(target, matrix, i, j - 1);


searchMatrix(target, matrix, 0, M) // Initially called at 'upper right' corner of matrix. M is number of columns.

Thoughts or alternate solution? Let us know in the comments below!