# 74. Search a 2D Matrix

You are given an `m x n` integer matrix `matrix` with the following two properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer `target`, return `true` if `target` is in `matrix` or `false` otherwise.

You must write a solution in `O(log(m * n))` time complexity.

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`
• `-10^4 <= matrix[i][j], target <= 10^4`

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

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

``````// Time Complexity O(m + n)
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int i = 0, j = (int)matrix[0].size() - 1;
while (i < matrix.size() && j >= 0) {
if (matrix[i][j] == target) return true;
if (matrix[i][j] > target) --j;
else ++i;
}
return false;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/74

Search a 2D Matrix II

Split Message Based on Limit

https://leetcode.com/problems/search-a-2d-matrix/

https://leetcode.com/problems/search-a-2d-matrix/discuss/26292/Java-clear-solution

https://leetcode.com/problems/search-a-2d-matrix/discuss/26220/Don't-treat-it-as-a-2D-matrix-just-treat-it-as-a-sorted-list

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation