Search a 2D Matrix

The matrix has the properties: each row is sorted, and the first element of each row is greater than the last element of the previous row. Determine if a target exists.

Function signature

func SearchMatrix(matrix [][]int, target int) bool

Inputs / outputs

• matrix: 2D matrix with row-major sorted order.
• target: value to search for.
• Return: true if target exists, else false.

Example

matrix = [
  [1,3,5,7],
  [10,11,16,20],
  [23,30,34,60],
]
target = 3
Output: true

Constraints

• 1 <= m, n <= 100

Core idea (near-solution)

Treat the matrix as a sorted 1D array of length m*n and apply binary search.

Invariant: each mid index maps to a valid (row, col) and preserves sorted order.

Algorithm (step-by-step)

1. Let m be rows, n be cols.
2. Binary search lo=0, hi=m*n-1.
3. For mid, map to r = mid / n, c = mid % n.
4. Compare matrix[r][c] with target and adjust bounds.

Correctness sketch

• Invariant: each mid index maps to a valid (row, col) and preserves sorted order.
• The valid answer lies within the maintained [lo, hi] range.
• Each comparison discards half the range that cannot contain an answer.
• When the loop ends, the remaining boundary/index is correct.

Trace (hand walkthrough)

Example input:
matrix = [
  [1,3,5,7],
  [10,11,16,20],
  [23,30,34,60],
]
target = 3
Output: true

Walk:
- treat as 1D length 12, target=3
- mid=5 -> value 11 >3 -> hi=5
- mid=2 -> value 5 >3 -> hi=2
- mid=1 -> value 3 -> found true

Pitfalls to avoid

• Incorrect row/column mapping.
• Using two separate binary searches when one is sufficient.

Complexity

• Time: O(log(m*n)).
• Extra space: O(1).

Implementation notes (Go)

• Guard against empty matrices if needed (though constraints ensure non-empty).