This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#74) before relying on it.

🔍 Search a 2D Matrix

An interactive visualization of how binary search efficiently finds a target in a sorted 2D matrix by treating it as a virtual 1D array.

Binary Search LeetCode 74 ↗ Medium

The Problem

You are given an m x n integer matrix with the following properties:

• Each row is sorted in non-decreasing order from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in the matrix, or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Interactive Visualization

Matrix (rows ; values ,)

Target

Preset

Speed:

Matrix

Flat index range: [0, 11] — Press Step to begin.

mid

eliminated

Current Step

Press Step or Play to begin.

Code

fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {    val m = matrix.size; val n = matrix[0].size    var lo = 0; var hi = m * n - 1    while (lo <= hi) {        val mid = (lo + hi) / 2        val row = mid / n; val col = mid % n        val v = matrix[row][col]        if (v == target)            return true        else if (v < target)            lo = mid + 1        else            hi = mid - 1    }    return false

def searchMatrix(matrix, target):    m, n = len(matrix), len(matrix[0])    lo, hi = 0, m * n - 1    while lo <= hi:        mid = (lo + hi) // 2        row, col = mid // n, mid % n        val = matrix[row][col]        if val == target:            return True        elif val < target:            lo = mid + 1        else:            hi = mid - 1    return False

How It Works

Key Insight

Because each row is sorted and the first element of each row is greater than the last element of the previous row, the entire matrix is effectively one long sorted array laid out row by row. We can run standard binary search on this virtual 1D array by converting between flat indices and (row, col) coordinates.

The Algorithm

Search space: lo = 0, hi = m * n - 1 — the flat indices of the virtual 1D array.
Each iteration: compute mid = (lo + hi) // 2, then map to matrix coordinates: row = mid // n, col = mid % n.
Compare: read matrix[row][col] and compare with the target.
If equal: return True — target found.
If value < target: discard the left half — lo = mid + 1.
If value > target: discard the right half — hi = mid - 1.
If lo > hi: the search space is exhausted — return False.

Complexity

Time O(log(m * n))

Space O(1)

Standard binary search over m * n elements. The flat-index-to-coordinate mapping is O(1) per iteration, so the total time is O(log(m * n)) with constant extra space.