Search a 2D Matrix: Flattened Binary Search Pattern

Learning Outcome

After this lesson, you should be able to map a one-dimensional binary-search index into matrix row and column.

Problem Statement

Given a matrix where each row is sorted and each row starts after the previous row ends, return true if target exists.

Brute Force Approach

Scan every cell in the matrix. This is simple but costs O(rows * cols).

Optimized Approach

Treat the matrix as a virtual sorted array of length rows * cols and binary search over virtual indexes.

Exact Pseudocode

rows = matrix.length
cols = matrix[0].length
l = 0
r = rows * cols - 1
while l <= r:
  mid = l + (r - l) / 2
  row = mid / cols
  col = mid % cols
  value = matrix[row][col]
  compare value with target
return false
  

Reference Code

class Solution:
    def searchMatrix(self, matrix, target):
        rows, cols = len(matrix), len(matrix[0])
        l = 0
        r = rows * cols - 1

        while l <= r:
            m = (l + r) // 2
            value = matrix[m // cols][m % cols]
            if value == target:
                return True
            if value < target:
                l = m + 1
            else:
                r = m - 1

        return False
  

Sample Dry Run

Complexity

Edge Cases

• One-row and one-column matrices still work.
• Use cols, not rows, for index mapping.
• Confirm the matrix ordering matches the flattened-array assumption.

Interview Checklist

• Map row = mid / cols and col = mid % cols.
• Do not physically flatten the matrix.
• Use safe midpoint calculation.

FAQs

The prompt guarantees every row starts after the previous row ends, so virtual order is sorted.

Then this exact flattened binary search assumption may not hold; use a different matrix search pattern.

Virtual indexing with binary search.