Search a 2D Matrix

•

문제 링크 : LeetCodeSearch a 2D Matrix - LeetCode

•

문제 설명 : 주어진 행렬에서 target 값이 존재하는지 확인

•

풀이 방법

◦

행 / 열에서 각각 이진 탐색을 하면 된다

▪

다만, 이진 탐색 시 break 조건을 적절하게 설정해야한다.

▪

target이 없는 경우도 있기 때문이다.

•

시간복잡도 : O(log(m∗n))O(log(m*n))O(log(m∗n))

•

성공 코드

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        left, right = 0, len(matrix) - 1

        # target이 속한 Row 이진 탐색
        while left <= right:
            mid = (left + right) // 2

            if matrix[mid][0] <= target <= matrix[mid][-1]:
                break
            elif target > matrix[mid][0]:
                left = mid + 1
            elif target < matrix[mid][0]:
                right = mid - 1

        target_row = mid
        left, right = 0, len(matrix[target_row]) - 1

        # target 범위 Row 이진 탐색
        while left <= right:
            mid = (left + right) // 2

            if target == matrix[target_row][mid]:
                return True
            elif target > matrix[target_row][mid]:
                left = mid + 1
            elif target < matrix[target_row][mid]:
                right = mid - 1

        return False
Python
복사