74. Search a 2D Matrix

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.

Example 1:

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

Example 2:

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

Constraints:

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 100

• -104 <= matrix[i][j], target <= 104

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        length = len(matrix[0])
        index = -1
        for rowIndex in range(len(matrix)):
            if matrix[rowIndex][0] <= target <= matrix[rowIndex][-1]:
                index = rowIndex
        if index == -1:
            return False
        return self.linear_search(matrix[index], target)
    
    def linear_search(self, nums, target):
        if target in nums:
            return True
        return False

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = len(matrix)
        col = len(matrix[0])
        minRow = 0
        maxRow = 0
        for r in range(row):
            if target <= matrix[r][col-1]:
                maxRow = r
            elif matrix[r][0] >= target:
                minRow = r
        for r in range(minRow, maxRow+1):
            for c in range(col):
                if matrix[r][c] == target:
                    return True
        return False