1
2

输入：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
输出：true

1
2

输入：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
输出：false

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 二分查找(z字形搜索)
    /// 1. 设置查找起点为(x,y) = (0, n-1)矩阵右上角;
    /// 2. 如果 target == matrix[x][y], 则找到target, 返回true;
    /// 3. 如果 target > matrix[x][y], 则target在当前元素下方, y+=1;
    /// 4. 否则 target < matrix[x][y], target在当前元素左侧, x-=1;
    pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
        let (m, n) = (matrix.len(), matrix[0].len());
        let (mut r, mut c) = (0, n - 1);
        while (0..m).contains(&r) && (0..n).contains(&c) {
            match target.cmp(&matrix[r][c]) {
                std::cmp::Ordering::Equal => return true,
                std::cmp::Ordering::Greater => r += 1,
                _ => c -= 1,
            }
        }

        return false;
    }
}
// @lc code=end

struct Solution;