Search a 2D Matrix

Problem

You are given an m x n matrix with two guarantees:

1. each row is sorted in ascending order;
2. the first integer of each row is greater than the last integer of the previous row.

Return true if target exists in the matrix, otherwise false.

Intuition

The matrix is not "2D" in any algorithmically interesting sense. Because every row starts after the previous row ends, the entire matrix is already sorted if you read it left to right, top to bottom.

That means you do not need a special matrix algorithm. You need a one-dimensional binary search plus a coordinate mapping:

• mid / cols gives the row;
• mid % cols gives the column.

The only extra work is handling the empty-matrix case cleanly.

Approach

impl Solution {
    pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
        if matrix.is_empty() || matrix[0].is_empty() {
            return false;
        }

        let cols = matrix[0].len();
        let mut lo = 0usize;
        let mut hi = matrix.len() * cols;

        while lo < hi {
            let mid= lo + (hi - lo) / 2;
            let value= matrix[mid / cols][mid % cols];

            if value < target {
                lo= mid + 1;
            } else if value > target {
                hi = mid;
            } else {
                return true;
            }
        }

        false
    }
}

function searchMatrix(matrix: number[][], target: number): boolean {
  if (matrix.length === 0 || matrix[0].length === 0) return false;

  const rows = matrix.length;
  const cols = matrix[0].length;
  let lo = 0;
  let hi = rows * cols;

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    const value = matrix[Math.floor(mid / cols)][mid % cols];

    if (value < target) {
      lo = mid + 1;
    } else if (value > target) {
      hi = mid;
    } else {
      return true;
    }
  }

  return false;
}

Trace

Search target = 13 in matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]:

The interval collapses with no equality hit, so the answer is false.

Edge cases

• Empty matrix — return false before indexing row 0.
• Single row — the algorithm degenerates to ordinary binary search.
• Single column — the same mapping still works because mid % cols is always 0.

Takeaway

Whenever a 2D structure has a global sorted order, flatten it before you overthink it. The real skill is recognizing when the data structure is a presentation detail, not an algorithmic constraint.