Search a 2D Matrix

Given m x n matrix that 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.

Write an efficient algorithm that searches for a value in this matrix. For example, consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true. Else, return false.


My Solution

Since the integers are sorted left to right and the last integer on the current row is always less than the first integer on the next row, we can treat this as a “normal” sorted array and perform binary search with some tricks.

  1. Likewise, init the two pointers left with 0 and right with m*n-1, where m is length of columns and n is length of rows
  2. Perform the usual binary search: find the middle value and cut the invariant half depending on greater or less than target. But, this time use the mid/n to select the row integer and mid%n to select the column integer

The complete code would be as below:

def search(matrix, target):
    """
    :type matrix: List[List[int]]
    :type target: int
    :rtype: bool
    """
    row, col = len(matrix), len(matrix[0])
    l, r = 0, row*col-1
        
    while l<=r:
        mid = (l+r)/2
        num = matrix[mid/col][mid%col]
        if num == target:
            return True
        if num > target:
            r = mid-1
        else:
            l = mid+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