Search a 2D Matrix

Sources: leetcode 74

Rating: medium

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.
def searchMatrix(matrix: List[List[int]], target: int) -> bool:
    # return if the target appears in matrix

Solution

The fact that the matrix is sorted in order immediately gives away that the intended algorithm is a binary search, just applied twice in both dimensions.

def searchMatrix(matrix, target):
    if len(matrix) == 0:
        return False
    # binary search through rows
    # binary search through columns

First, go through the rows from top t to bottom b in a binary search to locate the row where the target would be if it is in the matrix.

def searchMatrix(matrix, target):
    if len(matrix) == 0:
        return False
    t, b = 0, len(matrix) - 1
    while t < b:
        m = (t + b) // 2 + 1
        if matrix[m][0] == target:
            return True
        elif matrix[m][0] < target:
            t = m
        else:
            b = m - 1
    # binary search through columns

Next, use a binary search to locate the column between left l and right r.

def searchMatrix(matrix, target):
    if len(matrix) == 0:
        return False
    t, b = 0, len(matrix) - 1
    while t < b:
        m = (t + b) // 2 + 1
        if matrix[m][0] == target:
            return True
        elif matrix[m][0] < target:
            t = m
        else:
            b = m - 1
    l, r = 0, len(matrix[0]) - 1
    while l <= r:
        m = (l + r) // 2
        if matrix[t][m] == target:
            return True
        elif matrix[t][m] < target:
            l = m + 1
        else:
            r = m - 1
    # handle case for if target not found after search completes

If the binary search completes without finding the target, return false.

Final Code

def searchMatrix(matrix, target):
    if len(matrix) == 0:
        return False
    t, b = 0, len(matrix) - 1
    while t < b:
        m = (t + b) // 2 + 1
        if matrix[m][0] == target:
            return True
        elif matrix[m][0] < target:
            t = m
        else:
            b = m - 1
    l, r = 0, len(matrix[0]) - 1
    while l <= r:
        m = (l + r) // 2
        if matrix[t][m] == target:
            return True
        elif matrix[t][m] < target:
            l = m + 1
        else:
            r = m - 1
    return False

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s