Why can the matrix be searched as one array?

Each row is sorted and the first value of each row is greater than the last value of the row before. Reading the rows one after another therefore gives a single sorted sequence of m · n values, which binary search can handle directly.

How do you turn a flat index into a row and column?

With n columns, index i is at row i / n (integer division) and column i % n. Index 5 in a 3 × 4 matrix is row 1, column 1.

How is Search a 2D Matrix II different?

In Search a 2D Matrix II, rows and columns are each sorted but a row does not have to start after the previous row ends, so there is no single sorted order. Start at the top-right corner and move left or down, which takes O(m + n).

Search a 2D Matrix

Search a row-sorted matrix in O(log(m·n)) with one binary search over the matrix read as a flat sorted array.

MediumSolve on LeetCode

Problem Understanding

Search a 2D Matrix: an m × n matrix has each row sorted, and every row's first value is greater than the previous row's last value. Return whether target is in it, in O(log(m · n)) time.

Example: in [[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3 is present and 13 is not.

Attempt 1: Find the Row, Then Search It

Binary search the first column to find the only row that could hold the target, then binary search that row. That is O(log m + log n) = O(log(m · n)) too, but it is two searches with two sets of boundary cases. Seeing the whole matrix as one sorted array needs only one.

The Intuition: It Is Already One Sorted Array

Read the matrix row by row: 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60. Because each row starts above where the last one ended, that list is sorted. So run ordinary binary search on indices 0 to m · n - 1, and whenever you need the value at index i, look it up at row i / n, column i % n.

No flattened copy is built; the index arithmetic does the flattening on the fly.

Interactive Walkthrough

Each cell shows its flat index underneath. The search narrows lo and hi over those indices, cells outside the range are struck out, and mid lands on whichever row and column its index maps to.

Dry Run Table

Input: the example matrix, target = 3

lo	hi	mid	(row, col)	value	Move
0	11	5	(1, 1)	11	too big: hi = 4
0	4	2	(0, 2)	5	too big: hi = 1
0	1	0	(0, 0)	1	too small: lo = 1
1	1	1	(0, 1)	3	found

The Solution Template

Binary search over flat indices, mapped to (row, column) on each read.

Search a 2D Matrix Code

1var searchMatrix = function(matrix, target) {
2    const m = matrix.length, n = matrix[0].length;
3    let lo = 0, hi = m * n - 1;
4    while (lo <= hi) {
5        const mid = Math.floor((lo + hi) / 2);
6        const value = matrix[Math.floor(mid / n)][mid % n];
7        if (value === target) return true;
8        if (value < target) lo = mid + 1;
9        else hi = mid - 1;
10    }
11    return false;
12};

Edge Cases & Common Mistakes

Dividing by m instead of n: the row is mid / n, where n is the number of columns.
One row or one column: the same code works; it is just a plain array.
Target below the first or above the last value: the range empties and the answer is false.
Using this on Search a 2D Matrix II: that matrix is not one sorted sequence; use the top-right corner walk instead.

Summary

Because each row starts after the previous one ends, the matrix is a sorted array in disguise. Binary search the indices 0 to m · n - 1 and read index i at matrix[i / n][i % n].

More practice: DSA interview questions with answers · patterns cheat sheet

Find Minimum in Rotated Sorted Array

Search a 2D Matrix II