074.SearchA2DMatrix.md

tags: Array, Matrix, BinarySearch

#LeetCode 74 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.

Difficulty
Medium

Similar Problems
[LeetCode 240] Search a 2D Matrix II M

Analysis

Idea 1

Binary Search in vertically in a 2D array to determine which row contains the target value, then Binary Search in that row to find the target.

Idea 2

Since the 2d matrix is actually linear ordered, we can use only once Binary Search to find the target. As long as we take care of the converiton between 2d index and 1d index.

1. Cpp solution

two times binray search

class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        if (target < matrix[0][0] || target > matrix.back().back()) return false;
        int top = 0, bottom = matrix.size() - 1;
        while (top <= bottom) {
            int mid = (top + bottom) / 2;
            if (matrix[mid][0] == target) return true;
            else if (matrix[mid][0] < target) top = mid + 1;
            else bottom = mid - 1;
        }
        int tmp = bottom;
        int left = 0, right = matrix[tmp].size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (matrix[tmp][mid] == target) return true;
            else if (matrix[tmp][mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
};

2. Cpp solution

one binary search + 2d index convertion

class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        if (target < matrix[0][0] || target > matrix.back().back()) return false;
        int m = matrix.size(), n = matrix[0].size();
        int left = 0, right = m * n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (matrix[mid / n][mid % n] == target) return true;
            else if (matrix[mid / n][mid % n] < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
};

3. Go solution

func searchMatrix(matrix [][]int, target int) bool {

    m := len(matrix)
    if m == 0 {
        return false
    }
    n := len(matrix[0])
    if n == 0 {
        return false
    }

    left, right := 0, m*n-1
    for left <= right {
        mid := (left + right) / 2
        if matrix[mid/n][mid%n] == target {
            return true
        } else if matrix[mid/n][mid%n] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

Reference