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. Have you met this question in a real interview? Yes Example Consider the following matrix:

[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] Given target = 3, return true.

Solution: Convert to 1D array by using m%n and m/n.

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

    int m = matrix.length, n = matrix[0].length;
    int start = 0, end = matrix.length * matrix[0].length - 1;

    while(start <= end) {
        int mid = (start + end) / 2;
        int row = mid / n;
        int col = mid % n;
        int midVal = matrix[row][col];
        if(midVal == target) {
            return true;
        }
        else if(midVal > target) {
            end = mid - 1;
        }
        else {
            start = mid + 1;
        }
    }
    return false;
}

Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix, return the occurrence of it.

This matrix has the following properties:

Integers in each row are sorted from left to right. Integers in each column are sorted from up to bottom. No duplicate integers in each row or column. Example Consider the following matrix:

[
  [1, 3, 5, 7],
  [2, 4, 7, 8],
  [3, 5, 9, 10]
]

Given target = 3, return 2.

Solution:

public int searchMatrix(int[][] matrix, int target) {
    if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    int row = matrix.length - 1, col = 0;
    int res = 0;
    while(row >= 0 && col < matrix[0].length) {
        if(matrix[row][col] == target) {
            res++;
            row--;
            col++;
        }
        else if(matrix[row][col] > target) {
            row--;
        }
        else {
            col++;
        }
    }
    return res;
}