n0074_search_a_2d_matrix.rs

/**
 * [74] Search a 2D Matrix
 *
 * Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
 * 
 * 
 * 	Integers in each row are sorted from left to right.
 * 	The first integer of each row is greater than the last integer of the previous row.
 * 
 * 
 * Example 1:
 * 
 * 
 * Input:
 * matrix = [
 *   [1,   3,  5,  7],
 *   [10, 11, 16, 20],
 *   [23, 30, 34, 50]
 * ]
 * target = 3
 * Output: true
 * 
 * 
 * Example 2:
 * 
 * 
 * Input:
 * matrix = [
 *   [1,   3,  5,  7],
 *   [10, 11, 16, 20],
 *   [23, 30, 34, 50]
 * ]
 * target = 13
 * Output: false
 * 
 */
pub struct Solution {}

impl Solution {
    pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
        if matrix.is_empty() { return false }
        let (height, width) = (matrix.len(), matrix[0].len());
        if height < 1 || width < 1 { return false }
        let mut size = height * width;
        let mut base = 0_usize;
        while size > 1 {
            let half = size / 2;
            let mid = base + half;
            if target == matrix[mid/width][mid%width] {
                return true
            } else if (target > matrix[mid/width][mid%width]) {
                base = mid;
            }
            size -= half;
        }
        target == matrix[base/width][base%width]
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_74() {
        assert_eq!(
            Solution::search_matrix(
                vec![
                    vec![1,   3,  5,  7],
                    vec![10, 11, 16, 20],
                    vec![23, 30, 34, 50]
                ], 3
            ),
            true
        );
        assert_eq!(
            Solution::search_matrix(
                vec![
                    vec![1,   3,  5,  7],
                    vec![10, 11, 16, 20],
                    vec![23, 30, 34, 50]
                ], 13
            ),
            false
        );
    }
}