原题l链接：Leetcode 240. Search a 2D Matrix II
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 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 <= matrix[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
方法一：Z型搜索 思路：
核心的想法就是 不断缩小搜索范围
因为从上到下和从左到右都是排序好的
可以从右上角或者左下角（因为这两个位置具有 单调性 ）开始搜索
以从右上角开始搜索为例：
- 当前值比目标元素大时，说明没必要往下走了（往下走更大），那就向左走
- 当前值比目标元素小时，同理，往下走
这是一个能不断缩小搜索范围的过程，最终能得到结果
大佬的思路理解：
[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 = 9，如果我们从 15 开始遍历, cur = 15
target < 15, 去掉当前列, cur = 11
[1, 4, 7, 11],
[2, 5, 8, 12],
[3, 6, 9, 16],
[10, 13, 14, 17],
[18, 21, 23, 26]
target < 11, 去掉当前列, cur = 7
[1, 4, 7],
[2, 5, 8],
[3, 6, 9],
[10, 13, 14],
[18, 21, 23]
target > 7, 去掉当前行, cur = 8
[2, 5, 8],
[3, 6, 9],
[10, 13, 14],
[18, 21, 23]
target > 8, 去掉当前行, cur = 9, 遍历结束
[3, 6, 9],
[10, 13, 14],
[18, 21, 23]
作者：windliang
链接：https://leetcode.cn/problems/search-a-2d-matrix-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-5-4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
c++代码：
class Solution {
public:
bool searchMatrix(vector>& matrix, int target) {
// m行 n列
// 必须是一加一减, 能保证逐渐逼近答案
int m = matrix.size(), n = matrix[0].size();
int x = 0, y = n - 1;
// 找到或者出界就停止循环
while(x < m && y >= 0){
if(matrix[x][y] == target)
return true;
// 当前值比目标值大, 说明目标值可能在左边, 向左移动
if(matrix[x][y] > target)
y--;
// 否则就向下移动
else
x++;
}
return false;
}
};
复杂度分析：
- 时间复杂度：O(m+n)，做多能向左走n步，向下走m行
- 空间复杂度：O(1)
