Search in Matrix

74. Search a 2D Matrix

Example 1:

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

solution 1 and solution 2 are the same as the next question.

Solution 1: O(m*log n)

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:return False
        C = len(matrix[0])
        for row in matrix:
            i = bisect.bisect_left(row, target)
            if i==C:continue
            if target==row[i]:return True 
        return False

Solution 2: O(m+n)

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:return False
        j = -1
        for row in matrix:
            while j+len(row) and row[j]>target:j-=1
            if target==row[j]:return True
        return False

solution 3 (Olog(m*n))

This binary search is a little bit slower than the solution 2.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:return False
        R, C =len(matrix), len(matrix[0])
        def binary():
            l, r = 0, R*C-1
            while l<=r:
                m = (l+r)//2
                mid_val = matrix[m//C][m%C]
                if mid_val==target:return True
                elif mid_val<target:l+=1
                else:r-=1
            return False
        return binary()

240. Search a 2D Matrix II

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.

Solution 1: O(m*log n)

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:return False
        C = len(matrix[0])
        for row in matrix:
            i = bisect.bisect_left(row, target)
            if i==C:continue
            if target==row[i]:return True 
        return False

Solution 2: O(m+n)

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:return False
        j = -1
        for row in matrix:
            while j+len(row) and row[j]>target:j-=1
            if target==row[j]:return True
        return False