Search a 2D Matrix Visualizer & Step-by-Step Algorithm Solution

Treat an m x n row-sorted matrix as a virtual 1D sorted array [0 .. m*n - 1] and perform binary search.

Category: binary-search | Difficulty: Medium

Tags: Binary Search, 2D Matrix, Coordinate Mapping

Search a 2D Matrix

2D Matrix (3x4)
0
1
2
3
0
1
2
1
3
5
7
10
11
16
20
23
30
34
60
Active Cell
Active Row / Col / Box
Conflict / Subtracted
Highlighted / Subgrid
100%
state
target3
m3
n4
left0
right11
resultSearching
Initialization
1/14
Explanation

Start 2D binary search for target = 3 across a 3x4 sorted matrix (12 total cells).

Source Code
1function searchMatrix(matrix, target) {
2 const m = matrix.length;
3 const n = matrix[0].length;
4 let left = 0, right = m * n - 1;
5 while (left <= right) {
6 const mid = Math.floor((left + right) / 2);
7 const row = Math.floor(mid / n);
8 const col = mid % n;
9 const val = matrix[row][col];
10 if (val === target) {
11 return true;
12 } else if (val < target) {
13 left = mid + 1;
14 } else {
15 right = mid - 1;
16 }
17 }
18 return false;
19}