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

You are given an m x n integer matrix matrix with the following two properties:
Each row is sorted in non-decreasing order.The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.

1. 각 행은 오름차순으로 정렬되어 있음

2. 한 행의 첫 번째 값은 이전 행의 마지막 값보다 큼

O(log(m*n))으로 풀라고 명시되어 있어, 이진 탐색을 활용해야 하는 문제다.

 

 

풀이1 : Binary Search

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

        top, bot = 0, ROWS - 1
        while top <= bot:
            row = (top + bot) // 2
            if target > matrix[row][-1]:
                top = row + 1
            elif target < matrix[row][0]:
                bot = row - 1
            else:
                break

        if not (top <= bot):
            return False
        row = (top + bot) // 2
        l, r = 0, COLS - 1
        while l <= r:
            m = (l + r) // 2
            if target > matrix[row][m]:
                l = m + 1
            elif target < matrix[row][m]:
                r = m - 1
            else:
                return True
        return False

 

행렬에서 먼저 타겟 값을 포함할 수 있는 행을 찾은 후, 해당 행 내에서 이진 탐색을 수행한다.

행 -> 열의 탐색 순서를 따라서 직관적인 방식이다.

O(log N + log M)

 

 

풀이 2: Binary Search (One Pass)

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

        l, r = 0, ROWS * COLS - 1
        while l <= r:
            m = l + (r - l) // 2
            row, col = m // COLS, m % COLS
            if target > matrix[row][col]:
                l = m + 1
            elif target < matrix[row][col]:
                r = m - 1
            else:
                return True
        return False

2D 행렬을 1D 배열로 간주하여 하나의 이진 탐색으로 문제를 해결할 수 있다.

O(log N * M)