[LeetCode][Python] 74. Search a 2D Matrix

- 문제 링크: https://leetcode.com/problems/search-a-2d-matrix/

- 난이도: Medium

 

(0, 0)부터 (m, n)까지 non-decreasing 순서로 정렬된 2차원 배열에서 주어진 값이 존재하는지 찾는 문제다

O(log(m*n)) 시간 복잡도로 해결해야한다.

 

첫 열만 봤을 때, target 이하이면서 그 중 가장 큰 값이 있는 행에서 값을 이분탐색으로 찾으면 된다

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # find adequate row
        l, r = 0, len(matrix) - 1
        row_cand = -1
        while l <= r:
            mid = l + ((r-l) // 2)
            v = matrix[mid][0]
            if v == target:
                return True
            elif v < target:
                row_cand = mid
                l = mid + 1
            else:
                r = mid - 1

        if row_cand == -1:
            return False
        
        # for one row
        l, r = 0, len(matrix[0]) - 1
        while l <= r:
            mid = l + ((r-l) // 2)
            v = matrix[row_cand][mid]
            if v == target:
                return True
            elif v < target:
                l = mid + 1
            else:
                r = mid - 1
        return False

 

솔루션을 보니 더 간단한 방법도 있었는데, 사실 이게 일차원 배열이라고 생각하면 거기서 그냥 이분탐색 한번만 쭉 돌려도 된다

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])
        l, r = 0, rows * cols - 1
        while l <= r:
            mid = l + (r - l) // 2
            row = mid // cols
            col = mid % cols
            v = matrix[row][col]
            if v == target:
                return True
            elif v < target:
                l = mid + 1
            else:
                r = mid - 1
        return False