[LeetCode 74] Search a 2D Matrix

Question

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)

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;
}

Woodstock Blog

a tech blog for general algorithmic interview questions