Search a 2D Matrix Part II

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 in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.


My Solution

This is a bit different from the the 2D matrix that I posted before (where I could handle this using usual binary search). The idea would be starting from the most top right element (or bottom left, doesn’t matter), compare it with the target and reduce the range search. This is essentially called “diagonal binary search”.

From the above example, suppose the target is 12. The first element that we see, matrix[0][4] = 15, is greater than 12. Since this is greater, there is no way that 12 can appear in the same column numbers below this element are bigger than 15, so we eliminate this column in our search and move left to matrix[0][3]. Now we see that matrix[0][3] = 11 which is smaller than our target 12. Since this is smaller, there is no way that our target can appear in the same row 0 since all numbers on its left are smaller. Thus, we eliminate our search on this row by going down to matrix[1][3], we are done!

In case we are trying to find number that doesn’t exist in the matrix, the algorithm will keep going until it reaches the boundary of the matrix and return false. The sample code would be as below written in Python.

def search(matrix, target):
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n-1
        
    while row < m and col >= 0:
        if matrix[row][col] == target:
            return True
        if matrix[row][col] > target:
            col -= 1
        else:
            row += 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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s