Search for an Element in a Matrix

Problem: A m*n matrix with its each row and each column sorted in ascending order. Given a target element, find that element in the matrix or return null if not found.

Solution: The following gives an O(m+n) algorithm.

1. Start from matrix[0][n-1], compare it with the target element. If equal, return; if matrix[0][n-1] is smaller than the target value, go vertically down to next row (examine matrix[1][n-1]); if matrix[0][n-1] is bigger than the target value, go horizontally left to the previous column (examine matrix[0][n-2]).
2. Compare the current cell in the matrix with the target element. If equal, return; if current cell is smaller than the target value, go vertically down to next row. if current cell is bigger than the target value, go horizontally left to the previous column.
3. Stop when it reaches the last row or first column or the target element is found. 
4. We actually can use binary search here.