Search in a 2D Matrix - I | Binary Search of 2D

Welcome to the definitive study notes for Search in a 2D Matrix - I. In this chapter, we explore how to efficiently determine if a target value exists within a row-wise and column-wise sorted two-dimensional matrix. We will evolve our solution from a brute-force traversal down to an optimal binary search approach achieved through a clever mathematical mental model.

1. Problem Statement & Initial Definition

We are given a 2D matrix of dimensions $N \times M$ (where $N$ is the number of rows and $M$ is the number of columns) along with a target value.

• Matrix Property: Each row is sorted from left to right. Furthermore, the first element of each row is strictly greater than the last element of the previous row (in standard variations of this problem, though here we focus on the property where rows are sorted and can be treated sequentially).
• Goal: Find out if the target exists in the matrix.
  • If it exists, return true.
  • If it does not exist, return false.

Example Matrix ($N = 3, M = 4$)

Row 0: [ 3,  4,  7,  9 ]
Row 1: [12, 13, 16, 18 ]
Row 2: [20, 21, 23, 29 ]

• Indexing: 0-based indexing is used. Rows are indexed from $0$ to $N-1$ and columns from $0$ to $M-1$.

2. Approach 1: Extreme Brute-Force Traversal

The most intuitive and straightforward way to solve this problem is to visit every single element in the 2D matrix, checking whether it matches the target.

Algorithm

1. Outer loop i iterates from 0 to N - 1 (representing rows).
2. Inner loop j iterates from 0 to M - 1 (representing columns).
3. Check if Matrix[i][j] == target. If true, return true.
4. If the loops terminate without a match, return false.

Code Implementation (Brute Force)

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int n = matrix.size();
    int m = matrix[0].size();
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == target) {
                return true;
            }
        }
    }
    return false;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N \times M)$ because we visit every element in the grid.
• Space Complexity: $\mathcal{O}(1)$ as no extra data structures are used.

3. Approach 2: Row-wise Binary Search

Can we do better than $\mathcal{O}(N \times M)$ without changing our perspective of the 2D matrix? Yes. Since each individual row is already sorted, we do not need to scan every element linearly.

Core Insight

Instead of checking every element in a row, we can check the boundary elements of row i:

• First element: Matrix[i][0]
• Last element: Matrix[i][M - 1]

If our target lies between these two boundary values, the target must reside in this row. Because the row is sorted, we can perform a Binary Search directly on that specific 1D row.

Code Implementation

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int n = matrix.size();
    int m = matrix[0].size();
    
    for (int i = 0; i < n; i++) {
        // Check if target lies within the boundaries of the current row
        if (matrix[i][0] <= target && target <= matrix[i][m - 1]) {
            // Perform binary search on this 1D row
            return binarySearch(matrix[i], target);
        }
    }
    return false;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N + \log M)$. In the worst case, we might check the boundary of every row ($\mathcal{O}(N)$), and for one matching row, we perform binary search ($\mathcal{O}(\log M)$).
• Space Complexity: $\mathcal{O}(1)$.

4. Approach 3: Optimal Virtual Flattening (Binary Search in 2D)

Can we optimize our time complexity further down to $\mathcal{O}(\log(N \times M))$?

Core Mental Model & Analogy

Imagine taking the entire 2D matrix and hypothetically flattening it in your brain into a single continuous 1D sorted array of size $N \times M$.

2D Matrix:
[ 3,  4,  7,  9 ]
[ 12, 13, 16, 18 ]
[ 20, 21, 23, 29 ]

Hypothetically Flattened 1D Array (Indices 0 to 11):
Index:  0   1   2   3   4   5   6   7   8   9   10  11
Value: [3,  4,  7,  9, 12, 13, 16, 18, 20, 21,  23, 29]

If this were a real 1D array, we could simply initialize:

• low = 0
• high = (N * M) - 1
• mid = (low + high) / 2

And apply a standard binary search in $\mathcal{O}(\log(N \times M))$ time.

Crucial Reality Check: We must not physically flatten the matrix in memory, because copying $N \times M$ elements into a new 1D array would cost $\mathcal{O}(N \times M)$ time and space, defeating our performance goals. Instead, we perform the binary search virtually by mapping 1D indices directly to 2D coordinates on the fly.

5. The Mathematical Coordinate Conversion Formula

To execute a virtual binary search, whenever our binary search algorithm calculates a middle index (mid), we need a mathematical formula to translate that 1D mid index back into its corresponding 2D (row, col) coordinates in our matrix.

Deriving the Formulas

Given $M$ columns per row:

• Row Index (row): Determined by how many full rows of length $M$ have passed.

• Column Index (col): Determined by the remainder position within that row.

Walkthrough Example ($M = 4$ columns)

Let's test our formula with mid = 5:

• $\text{row} = 5 / 4 = 1$
• $\text{col} = 5 \pmod 4 = 1$
• Result: Coordinate (1, 1) corresponds to value 13 in our matrix. Checking index 5 in our hypothetical flattened array confirms it holds 13.

Let's test with mid = 11 (the last element):

• $\text{row} = 11 / 4 = 2$
• $\text{col} = 11 \pmod 4 = 3$
• Result: Coordinate (2, 3) corresponds to value 29.

6. Complete Flow Walkthrough of Optimal Search

Here is how the algorithm executes step-by-Step for target = 23:

7. Complete Optimal Code Implementation

Here is the clean, production-ready C++ code implementing the optimal virtual binary search approach:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        int m = matrix[0].size();
        
        int low = 0;
        int high = (n * m) - 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            // Map 1D hypothetical index to 2D coordinates
            int row = mid / m;
            int col = mid % m;
            
            if (matrix[row][col] == target) {
                return true;
            }
            else if (matrix[row][col] < target) {
                low = mid + 1; // Eliminate left half
            }
            else {
                high = mid - 1; // Eliminate right half
            }
        }
        
        return false;
    }
};

8. Approach Comparison Synthesis

Summary and Key Takeaways

• Problem Nature: Searching in a sorted 2D matrix can be mapped directly to searching in a sorted 1D array.
• Avoid Physical Flattening: Never copy a 2D matrix into a 1D array in memory, as the copying process itself requires $\mathcal{O}(N \times M)$ time.
• The Virtual Indexing Trick: Use mathematical division and modulo operators (mid / m and mid % m) to map 1D indices to 2D matrix coordinates instantly.
• Search Space Reduction: Binary search halves the search space at each iteration, yielding a logarithmic time complexity of $\mathcal{O}(\log(N \times M))$.
• Space Efficiency: The optimal virtual binary search solution operates in constant auxiliary space ($\mathcal{O}(1)$).
• Robust Range Management: Always calculate mid safely as low + (high - low) / 2 to prevent potential integer overflow bugs in production systems.