[Leetcode] Search a 2D Matrix

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 from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Use binary search twice. First search on the last column, if we could find the target then return true; otherwise we find the first element that bigger than target. If target exist then it could only exist on this row. So we do binary search on this row and try to find the target.

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if(m == 0)
            return false;
        int n = matrix[0].length;
        int left = 0, right = m - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(matrix[mid][n-1] == target)
                return true;
            else if(matrix[mid][n-1] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        int i = left;
        if(i >= m) // target is larger than the biggest element in the matrix
            return false;
        left = 0; right = n-1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(matrix[i][mid] == target)
                return true;
            else if(matrix[i][mid] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return false;
    }