Search a 2D Matrix

The "Search a 2D Matrix" problem is a common algorithmic challenge that involves searching for a target value in a 2D matrix where the matrix has certain properties that allow for more efficient search algorithms than a simple brute force approach.

Problem Statement

You are given a 2D matrix in which the integers in each row are sorted from left to right, and the first integer of each row is greater than the last integer of the previous row. The challenge is to determine if a given target value is present in the matrix.

Example of the Matrix

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

In this matrix, each row is sorted in increasing order, and each row starts with a number that is larger than any number in the previous row.

Objective

The objective is to find whether a given target number, say 3, exists in the matrix.

Efficient Search Strategies

Given the sorted nature of the rows and the increasing order of the leading elements of each row, two efficient methods are commonly used:

Binary Search on Rows and Columns: First, use binary search to identify the correct row by comparing the target with the first and last elements of each row. Once the correct row is identified, perform a binary search on that row to check if the target exists in that row.
Single Binary Search (Treat as a Sorted List): Treat the 2D matrix as a 1D sorted list and perform a single binary search. Calculate the mid-point in terms of the matrix using division and modulus operations to convert the 1D index back to 2D coordinates.
- To convert a 1D index mid into 2D indices (row, col), where cols is the number of columns:
```
row = mid / cols
col = mid % cols
```

Both methods rely on the properties of the matrix to efficiently reduce the search space and determine if the target is present.

Complexity

The time complexity of both methods is $O(\log m + \log n)$ or $O(\log (m \times n))$ , where $m$ is the number of rows and $n$ is the number of columns in the matrix, making the search quite efficient compared to a naive search approach.

This problem is popular in technical interviews as it tests understanding of binary search and how to adapt it to work in different contexts, such as 2D arrays.

Prev Next