# 240. Search a 2D Matrix II

Write an efficient algorithm that searches for a `target` value in an `m x n` integer `matrix`. The `matrix` has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example 1:

``````Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true
``````

Example 2:

``````Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false
``````

Constraints:

• `m == matrix.length`
• `n == matrix[i].length`
• `1 <= n, m <= 300`
• `-109 <= matix[i][j] <= 109`
• All the integers in each row are sorted in ascending order.
• All the integers in each column are sorted in ascending order.
• `-109 <= target <= 109`

``````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 x = matrix.size() - 1, y = 0;
while (true) {
if (matrix[x][y] > target) --x;
else if (matrix[x][y] < target) ++y;
else return true;
if (x < 0 || y >= matrix[0].size()) break;
}
return false;
}
};
``````

Github 同步地址：

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

Search a 2D Matrix

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

https://leetcode.com/problems/search-a-2d-matrix-ii/discuss/66139/C%2B%2B-search-from-top-right

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

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

×

Help us with donation