Question

link

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.

Stats

Frequency 3
Difficulty 3
Adjusted Difficulty 3
Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

[Search a 2D Matrix].

[Searching a 2D Sorted Matrix].

[Count negative in a 2D Sorted Matrix].

Analysis

This is a binary search question.

Solution

I did not use binary, but use the easier linear search. It still passed.

Code

my code revised (2D binary search)

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }
    int m = matrix.length;
    int n = matrix[0].length;
    // find target vertically from matrix[0] to matrix[m-1]
    int top = 0, bottom = m - 1;
    int mid;
    while (top + 1 < bottom) {
        mid = top + (bottom - top) / 2;
        if (matrix[mid][0] < target) {
            top = mid;
        }
        else {
            bottom = mid;
        }
    }
    // locate the row number
    int row = -1;
    if (matrix[top][0] <= target && target <= matrix[top][n-1]) {
        row = top;
    }
    else if (matrix[bottom][0] <= target && target <= matrix[bottom][n-1]) {
        row = bottom;
    }
    else {
        return false;
    }
    // now find target from matrix[row]
    int left = 0, right = n - 1;
    while (left + 1 < right) {
        mid = left + (right - left) / 2;
        if (matrix[row][mid] < target) {
            left = mid;
        }
        else {
            right = mid;
        }
    }
    return (matrix[row][left] == target || matrix[row][right] == target);
}

A good binary search code here (1D binary search)

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

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

    while(start<=end){
        int mid=(start+end)/2;
        int midX=mid/n;
        int midY=mid%n;

        if(matrix[midX][midY]==target)
            return true;
        if(matrix[midX][midY]<target){
            start=mid+1;
        }else{
            end=mid-1;
        }
    }
    return false;
}