leetcode/
search_a_2d_matrix.rs

1//! # 74. Search a 2D Matrix
2//!
3//! Medium
4//!
5//! You are given an `m x n` integer `matrix` matrix with the following two properties:
6//!
7//! - Each row is sorted in non-decreasing order.
8//! - The first integer of each row is greater than the last integer of the previous row.
9//! - Given an integer `target`, return `true` if `target` is in matrix or `false` otherwise.
10//!
11//! You must write a solution in `O(log(m * n))` time complexity.
12//!
13//! ## Examples
14//!
15//! - Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
16//! - Output: true
17//!
18//! - Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
19//! - Output: false
20//!
21//! ## Constraints
22//!
23//! - `m == matrix.length`
24//! - `n == matrix[i].length`
25//! - `1 <= m, n <= 100`
26//! - `-10^4 <= matrix[i][j], target <= 10^4`
27//!
28pub struct Solution;
29
30impl Solution {
31
32    /// Binary search
33    ///
34    /// O(log(m * n)) time complexity
35    pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
36        let rows = matrix.len() as isize;
37        let cols = matrix[0].len() as isize;
38
39        let mut start = 0;
40        let mut end = rows * cols - 1;
41
42        while start <= end {
43            let mid = (start + end) / 2;
44            let (i, j) = (mid / cols, mid % cols);
45            let mid_value = matrix[i as usize][j as usize];
46
47            if mid_value == target {
48                return true;
49            } else if mid_value < target {
50                start = mid + 1;
51            } else {
52                end = mid - 1;
53            }
54        }
55
56        false
57    }
58}
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test() {
66        let cases = vec![
67            (false, 0, vec![vec![1]]),
68            (true, 3, vec![
69                vec![ 1,  3,  5,  7],
70                vec![10, 11, 16, 20],
71                vec![23, 30, 34, 60],
72            ]),
73            (false, 13, vec![
74                vec![1,   3,   5, 7],
75                vec![10, 11, 16, 20],
76                vec![23, 30, 34, 50],
77            ]),
78        ];
79
80        for (expect, target, input) in cases {
81            assert_eq!(expect, Solution::search_matrix(input, target));
82        }
83    }
84}
leetcode/search_a_2d_matrix.rs

leetcode/
search_a_2d_matrix.rs
