Search a 2D Matrix¶

You are given an m x n 2-D integer array matrix and an integer target.

Each row in matrix is sorted in non-decreasing order. The first integer of every row is greater than the last integer of the previous row. Return true if target exists within matrix or false otherwise.

Can you write a solution that runs in O(log(m * n)) time?

Example 1:

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10

Output: true Example 2:

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 15

Output: false

Solution¶

Binary Search Rows: Find the potential row containing the target by comparing the target with first and last elements of each row, narrowing the search range.
Binary Search Column: Once the potential row is identified, perform a binary search within that row to find the exact target.
Time Complexity: O(log(m) + log(n)), where m is number of rows and n is number of columns.

In [4]:

def search2dmatrix(matrix, target):
    top,bottom=0,len(matrix)-1
    while top<=bottom:
        row = (top+bottom)//2
        if target<matrix[row][0]:
            bottom=row-1
        elif target>matrix[row][-1]:
            top=row+1
        else:
            break
        
    if not(top<=bottom):
        return False
    
    l,r=0,len(matrix[row])-1
    while l<=r:
        mid=(l+r)//2
        if target<matrix[row][mid]:
            r=mid-1
        elif target>matrix[row][mid]:
            l=mid+1
        else:
            return True
    
    return False

In [5]:

search2dmatrix([[1,2,4,8],[10,11,12,13],[14,20,30,40]],10)

Out[5]:

True

In [6]:

search2dmatrix([[1,2,4,8],[10,11,12,13],[14,20,30,40]],15)

Out[6]:

False

In [ ]: