Search an Element in a Sorted 2D Matrix - Visualization

Matrix - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

You are given a 2D matrix of integers with the following properties:

  • Each row is sorted in ascending order.
  • The first integer of each row is greater than the last integer of the previous row.

Your task is to determine whether a given target number exists in the matrix.

If the number exists, return true; otherwise, return false.

Examples❯

Matrix Target Output Description
[[1, 4, 7, 10, 13],[14, 17, 20, 23, 26],[27, 30, 33, 36, 39],[40, 43, 46, 49, 52],[53, 56, 59, 62, 65]]
36 true
36 exists in the third row and fourth column
[[1, 3, 5],[7, 9, 11],[13, 15, 17]]
9 true
9 exists in the second row
[[1, 3, 5],[7, 9, 11],[13, 15, 17]]
6 false 6 is not present in any row
[[2, 4, 6]]
4 true
Single row matrix, 4 is present
[[2, 4, 6]]
5 false Single row matrix, 5 is not present
[[2], [5], [8], [11]]
11 true
Single column matrix, 11 is the last element
[[2], [5], [8], [11]]
3 false Single column matrix, 3 is not present
[] 1 false Empty matrix, nothing to search
[[]] 0 false Matrix with empty row, no data to search

Solution❯

Understanding the Problem

We are given a 2D matrix and a target number. The matrix has two special properties:

  • Each row is sorted in increasing order from left to right.
  • The first number of each row is greater than the last number of the previous row.

This means if we "flatten" the matrix, the elements form a fully sorted 1D array. Our task is to determine whether the target number exists in the matrix. A beginner might think of scanning every row and column, but that would be inefficient. Instead, we will use a binary search approach that treats the entire 2D matrix as a sorted 1D list — without actually flattening it.

Step-by-Step Solution with Example

step 1: Represent the matrix and target


matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
]
target = 3

We want to check whether the number 3 exists in this matrix.

step 2: Understand the matrix as a virtual 1D array

The matrix has m = 3 rows and n = 4 columns. So the total number of elements is m × n = 12.

Imagine indexing this matrix from 0 to 11, like a normal 1D array. The key idea is:

  • row = Math.floor(index / n)
  • col = index % n

This lets us map any 1D index to a 2D coordinate in the matrix.

step 3: Initialize binary search

We set start = 0 and end = m × n - 1 = 11.

We will now perform binary search between these indices.

step 4: Perform the binary search loop

Repeat the following until start > end:

  1. Find the middle index: mid = Math.floor((start + end) / 2)
  2. Map this index to 2D: row = Math.floor(mid / n), col = mid % n
  3. Check matrix[row][col] against the target:
    • If it matches → return true
    • If it’s less than the target → move to right half: start = mid + 1
    • If it’s more than the target → move to left half: end = mid - 1

For our example, 3 is found at index 1 (which maps to row 0, column 1).

step 5: Return the result

If the binary search completes without finding the target, return false.

Edge Cases

  • Empty matrix: If the matrix is [], return false. No data to search.
  • Matrix with empty rows: For example, [[]] → no columns → return false.
  • Target smaller than the smallest element: return false.
  • Target greater than the largest element: return false.
  • These checks help us avoid unnecessary work and prevent runtime errors.

Finally

This approach is efficient and elegant. By treating the 2D matrix as a virtual 1D sorted array, we leverage binary search for O(log(m × n)) time complexity. This is especially helpful for large matrices.

For beginners, it's important to understand how index mapping works and how binary search helps us reduce the search space efficiently. Always check for edge cases first, then implement the main logic clearly and step by step.

Algorithm Steps❯

  1. Let the matrix have m rows and n columns.
  2. Initialize start = 0 and end = m * n - 1.
  3. While start ≤ end:
  4. → Compute mid = (start + end) / 2.
  5. → Convert mid to 2D coordinates: row = mid / n, col = mid % n.
  6. → If matrix[row][col] == target, return true.
  7. → If matrix[row][col] < target, move start = mid + 1.
  8. → If matrix[row][col] > target, move end = mid - 1.
  9. Return false if target not found.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdbool.h>

bool searchMatrix(int matrix[][4], int rows, int cols, int target) {
    int start = 0, end = rows * cols - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        int row = mid / cols;
        int col = mid % cols;

        if (matrix[row][col] == target) return true;
        else if (matrix[row][col] < target) start = mid + 1;
        else end = mid - 1;
    }
    return false;
}

int main() {
    int matrix[3][4] = {
        {1, 3, 5, 7},
        {10, 11, 16, 20},
        {23, 30, 34, 60}
    };
    int target = 3;
    printf("Found: %s\n", searchMatrix(matrix, 3, 4, target) ? "true" : "false");
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)The target is found at the very first middle index.
Average CaseO(log (m * n))The binary search is applied over a virtual 1D array of m * n elements.
Worst CaseO(log (m * n))The binary search checks until one element is left, typical of a logarithmic search space.

Space Complexity❯

O(1)

Explanation: The algorithm uses constant space, no extra data structures are used apart from a few variables.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...