Search an Element in a Sorted 2D Matrix Optimal Approach using Binary Search

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.

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.

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.

O(1)

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