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.

Why this is worth learning

Row-major order is globally sorted only because the next row starts above the previous row’s last element. This stronger promise permits one binary search over virtual flattened indices.

Before coding: one-minute experiment

Why can [[1,4],[2,5]] not be treated as the sorted virtual array [1,4,2,5], even though its rows and columns are sorted?

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)

A full cell scan uses O(mn) comparisons. An allocated flattened copy would make ordinary binary search convenient but still take O(mn) work to create. The matrix already supplies the same global row-major ordering, so compute the coordinates of each inspected flat index instead. This removes the copy; independently sorted rows and columns would not justify the same discards.

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

Invariant: if target is present, at least one matching flat index remains in the inclusive interval [lo,hi]. Indices before lo are too small and indices after hi are too large.

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

For m rows and n columns, flattened index k maps bijectively to (k/n,k%n). The within-row ordering and cross-row boundary condition make the virtual length-mn array sorted. Ordinary binary-search comparisons therefore discard only positions that cannot hold target. Mapping a midpoint does not allocate a flattened copy, and the search interval shrinks until an equal value is found or no positions remain. A matrix whose rows and columns are individually sorted but whose row ranges overlap does not satisfy this proof and needs a different search strategy.

Trace (hand walkthrough)

Use rows [1,3,5,7], [10,11,16,20], [23,30,34,60] and target 3. There are four columns, so flat index k maps to (k/4,k%4).

lo	hi (inclusive)	mid	Cell / value	Update
0	11	5	(1,1) / 11	hi=4
0	4	2	(0,2) / 5	hi=1
0	1	0	(0,0) / 1	lo=1
1	1	1	(0,1) / 3	return true

This loop excludes a disproved midpoint with mid-1 or mid+1; it does not use the lower-bound update hi=mid.

Pitfalls to avoid

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

Debugging lens

Use column count in both quotient and remainder. Test one row and one column. Do not silently replace the specified row-major ordering with a different matrix-search problem.

Complexity

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

Implementation notes (Go)

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

Reconstruction checkpoint

Why can [[1,4],[2,5]] not be treated as the sorted virtual array [1,4,2,5], even though its rows and columns are sorted?

Model answer

The second row starts at 2, which is not greater than the previous row’s last value 4. The virtual array is unsorted, so binary-search discards would not be justified.

Return to Binary Search · Module quiz