[leetcode] 이진탐색 74. Search a 2D Matrix

다음 두 가지 속성을 가진 m x n 정수 행렬이 제공됩니다:
각 행은 감소하지 않는 순서로 정렬됩니다.
각 행의 첫 번째 정수가 이전 행의 마지막 정수보다 큽니다.
target 정수값이 지정되면 대상이 행렬에 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
솔루션은 O(log(m * n)) 시간 복잡도로 작성해야 합니다.

 

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

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

 

class Solution:

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

        if not matrix or not matrix[0]:

            return False

        M = len(matrix)

        N = len(matrix[0])

        left = 0

        right = M*N-1

        while left <= right:

            mid = (left+right)//2

            mid_elem = matrix[mid//N][mid%N]

            if target == mid_elem:

                return True

            elif target > mid_elem :

                left = mid+1

            else:

                right = mid - 1

        return False