[DSA][Binary Search] 02. Search a 2D Matrix

LeetCode 74

 

02. 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.

 

 

[질문하기]

- 행렬의 크기 m과 n은 최대 얼마까지 주어질 수 있나요? (l+r이 오버플로우를 일으킬 수 있는지)

 

 

[아이디어]

- 2차원 배열이 1차원이라고 가정하고 mid를 계산한 후 row, col 인덱스로 변환하자.

 

 

[풀이 1] Binary Search

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

        l, r = 0, ROW * COL - 1
        while l <= r:
            mid = l + (r - l) // 2
            midX = mid // COL
            midY = mid % COL
            if matrix[midX][midY] == target:
                return True
            elif matrix[midX][midY] > target:
                r = mid - 1
            else:
                l = mid + 1
        return False

주어진 배열은 이미 오름차순으로 정렬되어 있기 때문에, 이진 탐색(Binary Search) 알고리즘을 사용하면 target 값을 효율적으로 찾을 수 있다. 1차원 배열과 똑같이 m * n 배열에 대해 이진 탐색을 하되,  2차원이기 때문에 mid 인덱스를 2차원 인덱스로 변환하는 과정만 추가해 주면 된다. 배열이 1차원인지 2차원인지만 다르기 때문에 행렬을 1차원 배열처럼 취급하여 탐색을 진행하고, 중간 인덱스(mid)를 2차원 좌표로 변환하여 비교하는 방식만 추가하면 된다.

 

 

⏱️ 시간복잡도

행렬의 크기 m * n에 대해 이진탐색하는 것이므로 O(log(m*n))의 시간 복잡도를 가진다.

🧠 공간복잡도

추가적인 공간을 사용하지 않고, 주어진 행렬에서 인덱스를 계산하는 데 필요한 변수만을 사용하기 때문에 O(1)의 공간 복잡도를 갖는다.