Search a 2d matrix

Array Binary Search Matrix

53.6% acceptance

Jan 12, 2026

17784

480

You are given an m x n integer matrix matrix with the following two properties: Each row is sorted in non-decreasing order. The first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in matrix or false otherwise. You must write a solution in O(log(m * n)) time complexity.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    let m = matrix.len();
    let n = matrix[0].len();
    let mut left = 0;
    let mut right = (m * n) as i32 - 1;
    
    while left <= right {
      let mid = left + (right - left) / 2;
      let row = (mid as usize) / n;
      let col = (mid as usize) % n;
      let val = matrix[row][col];
      
      if val == target {
        return true;
      } else if val < target {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    
    false
  }
}