Search a 2D Matrix

[ymolliks]

Ideas

1. Binary Search

Solution

After some inspection, it becomes clear that this problem is much easier if we treat the matrix as a sorted array. And then, we search for the $\tt target$ value using a simple binary search as we do for any regular sorted array.

Implementation

class Solution {
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();

        int l = 0, r = m * n - 1;
        while (l <= r) {
            int md = (l + r) >> 1;
            int rw = md / n, cl = md % n;
            if (matrix[rw][cl] == target)
                return true;
            if (matrix[rw][cl] > target)
                r = md - 1;
            else l = md + 1;
        }
        return false;
    }
};

Complexity

Time: $\tt O(\log n)$

Space: $\tt O(1)$

[ymolliks]

Search a 2D Matrix