LeetEye LeetEye
Medium Binary Search ~5 min

Search a 2D Matrix

binary-search search-a-2d-matrix

Problem

You are given an m x n integer matrix matrix with the following two properties:
- Each row is sorted in non-decreasing order.
- The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Examples

Example 1
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Key Insight

Treat the 2D matrix as a 1D sorted array. Use index conversion.

Matrix with sorted rows and row-to-row ordering = one sorted array. Binary search with index conversion: row = mid/cols, col = mid%cols.

How to Approach This Problem

Pattern Recognition: When you see keywords like search a 2d matrix binary-search, think Binary Search.

Step-by-Step Reasoning

1 Given the two properties, the entire matrix when read row by row is:
Answer: Fully sorted
Each row is sorted, and row i's last element < row i+1's first element. So all elements are in ascending order.
2 For an m×n matrix, how many elements total?
Answer: m × n
m rows, n elements each = m × n total.
3 For a 1D index i in a matrix with n columns, the row is:
Answer: i / n (integer division)
After every n elements, we move to the next row. i / n gives the row number.
4 For a 1D index i in a matrix with n columns, the column is:
Answer: i % n
Position within the row cycles every n elements. i % n gives column.
5 Binary search should search indices from:
Answer: 0 to m×n-1
Total m×n elements, indices 0 through m×n-1.
6 Another valid approach is:
Answer: Binary search to find the row, then binary search within the row
Two binary searches: O(log m) + O(log n) = O(log(m×n)). Same complexity!

Solution

def searchMatrix(matrix: List[List[int]], target: int) -> bool:
    if not matrix:
        return False
    
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        row, col = mid // n, mid % n
        val = matrix[row][col]
        
        if val == target:
            return True
        elif val < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return False

Complexity Analysis

Time O(log(m*n))
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Binary Search problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye