74. Search a 2D Matrix

Problem

Write an efficeint algorithm that searches for a value target in an mxn integer matrix 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(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        row = 0
        for i in range(len(matrix)) :
            if matrix[i][-1] >= target :
                row = i
                break
        
        tmp = matrix[row]
        left= 0
        right = len(tmp)-1
        while left <= right :
            mid = (left + right) // 2
            
            if tmp[mid] == target :
                return True
            elif tmp[mid] < target :
                left = mid + 1
            else :
                right = mid - 1
        return False