74. Search a 2D Matrix

74. Search a 2D Matrix (Medium)

Write an efficient algorithm that searches for a value target in an m x n integer matrix 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.

 

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

Companies:
Amazon, Facebook, Microsoft, Bloomberg, Apple

Related Topics:
Array, Binary Search, Matrix

Similar Questions:

• Search a 2D Matrix II (Medium)

Solution 1. Binary Search

// OJ: https://leetcode.com/problems/search-a-2d-matrix/
// Author: github.com/lzl124631x
// Time: O(log(MN))
// Space: O(1)
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& A, int target) {
        if (A.empty() || A[0].empty()) return false;
        int L = 0, R = A.size() - 1;
        while (L <= R) {
            int M = (L + R) / 2;
            if (A[M][0] == target) return true;
            if (A[M][0] < target) L = M + 1;
            else R = M - 1;
        }
        if (R == -1) return false;
        int row = R;
        L = 0, R = A[0].size() - 1;
        while (L <= R) {
            int M = (L + R) / 2;
            if (A[row][M] == target) return true;
            if (A[row][M] < target) L = M + 1;
            else R = M - 1;
        }
        return false;
    }
};

Solution 2. Binary Search

L <= R template:

// OJ: https://leetcode.com/problems/search-a-2d-matrix/
// Author: github.com/lzl124631x
// Time: O(log(MN))
// Space: O(1)
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& A, int target) {
        int M = A.size(), N = A[0].size(), L = 0, R = M * N - 1;
        while (L <= R) {
            int M = (L + R) / 2, i = M / N, j = M % N;
            if (A[i][j] == target) return true;
            if (A[i][j] < target) L = M + 1;
            else R = M - 1;
        }
        return false;
    }
};

L < R template:

// OJ: https://leetcode.com/problems/search-a-2d-matrix/
// Author: github.com/lzl124631x
// Time: O(log(MN))
// Space: O(1)
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& A, int target) {
        int M = A.size(), N = A[0].size(), L = 0, R = M * N - 1;
        while (L < R) {
            int M = (L + R) / 2, i = M / N, j = M % N;
            if (A[i][j] < target) L = M + 1;
            else R = M;
        }
        return A[L / N][L % N] == target;
    }
};

Solution 3.

// OJ: https://leetcode.com/problems/search-a-2d-matrix/
// Author: github.com/lzl124631x
// Time: O(M + N)
// Space: O(1)
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& A, int target) {
        if (A.empty() || A[0].empty()) return false;
        int M = A.size(), N = A[0].size(), i = 0, j = N - 1;
        while (i < M && j >= 0) {
            if (A[i][j] == target) return true;
            if (A[i][j] < target) ++i;
            else --j;
        }
        return false;
    }
};