Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

We track the number column by column. For each column, we start from the bottom, if the last number is smaller than target, we can go to the next column. Other wise we going up and find the number.

public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return false;
        int len = matrix.length, hei = matrix[0].length;

        for (int i = 0; i < len; i++) {
            int j = hei - 1;
            while (j >= 0 && matrix[i][j] > target)
                j--;
            if (j < 0) {
                return false;
            }
            if (j >= 0 && matrix[i][j] == target)
                return true;
        }
        return false;
    }