AlgoViz
HomeBinary Search

Search a 2

Medium

Treat the matrix as one flat sorted array

Problem

Given a 2D matrix that is fully sorted (each row sorted, and every row starts after the previous row ends), determine whether a target value exists in it.

In simple words

Treat the sorted grid as one long sorted list and binary-search using row = index/cols, col = index%cols.

The idea

When every row starts after the previous row ends, the whole matrix is one sorted sequence. Binary search indices 0..(r·c - 1) and convert each mid to a cell with divide and modulo.

The trick

  • row = mid / cols, col = mid % cols.
  • Only valid for the fully sorted variant; the row/column-sorted one needs the staircase walk.
  • O(log(r·c)).
1
3
5
7
10
11
16
20
23
30
34
60
target16

Step 1 of 8. Brute force: look at every cell until you find 16. target 16.

1/8
Brute force
timeO(m·n)spaceO(1)

Scan every cell.

1for (let r = 0; r < R; r++)2  for (let c = 0; c < C; c++)3    if (mat[r][c] === target) return true;

Input

grid
3 × 4

Memory

at
—
cells marked
0
target
16

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output:
true
Explanation:
3 is in the first row.

Example 2

Input:
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output:
false
Explanation:
13 is nowhere → false.

Example 3

Input:
matrix = [[1]], target = 1
Output:
true
Explanation:
Single cell match.

Constraints

  • 1 <= m, n <= 100
  • -10^4 <= matrix[i][j], target <= 10^4

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.