MediumBlind75ArrayBinary Search

Search a 2D Matrix

You are given an m x n integer matrix where each row is sorted and the first integer of each row is greater than the last integer of the previous row. Search for a target value.

Examples

Input
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output
true

3 is found in the matrix.

Input
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output
false

13 is not in the matrix.

Constraints

  • •m == matrix.length
  • •n == matrix[i].length
  • •1 <= m, n <= 100
  • •-10^4 <= matrix[i][j], target <= 10^4

Approaches

Search through every element in the matrix.

CodeT: O(m * n) | S: O(1)
def search_matrix(matrix, target):
    for row in matrix:
        for val in row:
            if val == target:
                return True
    return False

Use binary search on each row.

CodeT: O(m * log n) | S: O(1)
def search_matrix(matrix, target):
    for row in matrix:
        left, right = 0, len(row) - 1
        while left <= right:
            mid = (left + right) // 2
            if row[mid] == target:
                return True
            elif row[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
    return False

Treat the 2D matrix as a sorted 1D array.

Diagram

matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]] Flat: [1,3,5,7,10,11,16,20,23,30,34,60] Binary search: target=3 -> found at index 1 matrix[1//4][1%4] = matrix[0][1] = 3
CodeT: O(log(m * n)) | S: O(1)
def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1
    while left <= right:
        mid = (left + right) // 2
        val = matrix[mid // n][mid % n]
        if val == target:
            return True
        elif val < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

Complexity Comparison

Linear Search
T: O(m * n)S: O(1)

Search through every element in the matrix.

Binary Search per Row
T: O(m * log n)S: O(1)

Use binary search on each row.

Flattened Binary Search
T: O(log(m * n))S: O(1)

Treat the 2D matrix as a sorted 1D array.

Common Mistakes

Not handling empty matrix or empty rows

Using the wrong formula to convert 1D index to 2D coordinates

Binary search on rows first, then columns (less efficient)

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems