# Search a 2D Matrix

- **Canonical ID**: `search-a-2d-matrix`
- **Canonical URL**: https://dsacheatsheet.com/problems/search-a-2d-matrix
- **Difficulty**: medium
- **Patterns**: Binary Search
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/search-a-2d-matrix/

## 1. Core Invariant / The Trick

Treat the strictly row-major sorted `M x N` matrix as a flattened sorted 1D array `[0 .. M*N - 1]`, mapping index `mid` back to `(mid // N, mid % N)`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(log(M * N))`
- **Space Complexity**: `O(1)`
- **Proof**: Single binary search over virtual 1D coordinates avoids two nested searches.

## 3. Minimal Idiomatic Code

### Python
```python
def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    rows, cols = len(matrix), len(matrix[0])
    l, r = 0, rows * cols - 1
    while l <= r:
        m = (l + r) // 2
        v = matrix[m // cols][m % cols]
        if v == target: return True
        if v < target: l = m + 1
        else: r = m - 1
    return False
```

### TypeScript
```typescript
export function searchMatrix(matrix: number[][], target: number): boolean {
  const rows = matrix.length, cols = matrix[0].length;
  let l = 0, r = rows * cols - 1;
  while (l <= r) {
    const m = l + ((r - l) >> 1);
    const v = matrix[Math.floor(m / cols)][m % cols];
    if (v === target) return true;
    if (v < target) l = m + 1; else r = m - 1;
  }
  return false;
}
```

### C++
```cpp
bool searchMatrix(vector<vector<int>>& mat, int target) {
    int r = mat.size(), c = mat[0].size(), lo = 0, hi = r * c - 1;
    while (lo <= hi) {
        int m = lo + (hi - lo) / 2, v = mat[m / c][m % c];
        if (v == target) return true;
        v < target ? lo = m + 1 : hi = m - 1;
    }
    return false;
}
```

### Java
```java
boolean searchMatrix(int[][] mat, int target) {
    int r = mat.length, c = mat[0].length, lo = 0, hi = r * c - 1;
    while (lo <= hi) {
        int m = lo + (hi - lo) / 2, v = mat[m / c][m % c];
        if (v == target) return true;
        if (v < target) lo = m + 1; else hi = m - 1;
    }
    return false;
}
```

### Go
```go
func searchMatrix(mat [][]int, target int) bool {
    r, c := len(mat), len(mat[0])
    lo, hi := 0, r*c-1
    for lo <= hi {
        m := lo + (hi-lo)/2; v := mat[m/c][m%c]
        if v == target { return true }
        if v < target { lo = m + 1 } else { hi = m - 1 }
    }
    return false
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Note `col = mid % cols` uses `cols` (N), NOT rows (M).

### Follow-ups
- Search a 2D Matrix II (rows and cols sorted independently): start at top-right staircase in O(M + N).