Matrix Search

Fully Sorted Matrix

When rows are sorted and each row starts after the previous row ends, treat the matrix as a single sorted array. Map index mid to row=mid/cols, col=mid%cols. Standard binary search, O(log(m·n)).

O(log(m*n))

O(1)

How It Works

When every row of a matrix is sorted and the first element of each row is greater than the last element of the previous row, the whole matrix is one sorted sequence laid out in row-major order. That means an ordinary binary search works — you just translate the 1D midpoint index into 2D coordinates with row = mid / cols and col = mid % cols, and compare matrix[row][col] against the target.

This virtual flattening avoids materializing a copy of the matrix, so the search runs in O(log(m*n)) time and O(1) space, versus O(m*n) for a full scan. The only real pitfall is mixing up the division and modulo when converting indices, or applying this technique to a matrix that is only row-and-column sorted, where the global ordering assumption breaks and the staircase search is needed instead.

Step-by-Step Visualization

3x3 fully sorted matrix as 1D array

Target11

1/3

Code

Java

static boolean searchMatrix(int[][] matrix, int target) {
  int m = matrix.length, n = matrix[0].length;
  int left = 0, right = m * n - 1;

  while (left <= right) {
    int mid = left + (right - left) / 2;
    int val = matrix[mid / n][mid % n];
    if (val == target) return true;
    if (val < target) left = mid + 1;
    else right = mid - 1;
  }
  return false;
}

Tips & Gotchas

1Treat the 2D matrix as a 1D sorted array

2Map 1D index to 2D: row = idx / cols, col = idx % cols

3Apply standard binary search on the virtual 1D array

Practice Problems

1Search a 2D Matrix
2Kth Smallest Element in a Sorted Matrix
3Median in a Row-Wise Sorted Matrix

About the Matrix Search Pattern

Find a target value in a matrix with some sorted property. The sorting enables techniques faster than scanning every cell.

Key insight

For traversal: use direction arrays dx=[0,0,1,-1], dy=[1,-1,0,0]. For sorted matrix search, start from top-right corner. For grid DP, fill row by row — current cell depends on top and left.

Common Matrix Interview Problems

Spiral Matrix
Rotate Image
Search a 2D Matrix
Number of Islands
Maximal Square
Set Matrix Zeroes
Word Search

Frequently Asked Questions

How is this different from searching a row-and-column sorted matrix?

This technique requires a stronger property: each row must begin after the previous row ends, making the matrix one globally sorted list. If rows and columns are only sorted independently (as in Search a 2D Matrix II), there is no single sorted order, so you need the O(m+n) staircase search instead.

Why not binary search each row separately?

Searching each row costs O(m log n), which is worse than O(log(m*n)) = O(log m + log n) when the matrix is fully sorted. Per-row binary search only becomes reasonable when the global ordering property does not hold and you cannot use the flattened view.