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

https://leetcode.com/problems/search-a-2d-matrix/submissions/

Search a 2D Matrix - LeetCode

생각

2차원 배열에서 target 원소가 있는지 확인하는 문제입니다. 이때 효율적인 알고리즘을 작성하라는게 문제의 핵심입니다.

 

주어진 조건에서, row들이 정렬되있기 때문에 처음 시도는 특정 행을 선택하여 그 행에서 이진탐색을 통해 M*O(logn) 의 시간복잡도를 가지는 알고리즘을 구현했습니다.

Description을 보니 O(logM+logN)까지 줄일 수 있는 방법이 있었습니다. 단순히 row를 반복문을 돌아서 탐색하는게 아니라, row 탐색도 이진탐색을 통해 수행하면 됩니다.

 

Python Code1

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for i in range(len(matrix)):
            if matrix[i][0] <= target <= matrix[i][-1]:
                #binary search
                temp = matrix[i]
                return self.binarySearch(temp,target)
                
    
    def binarySearch(self, row, target):
        left = 0
        right = len(row)-1
        while left <= right:
            mid = (left+right) // 2
            if row[mid] == target:
                return True
            elif row[mid] > target:
                right = mid-1
            else:
                left = mid+1
        return False

 

 

Python Code2

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        R = len(matrix)
        C = len(matrix[0])
        
        top, bottom = 0, R-1
        while top <= bottom:
            row_mid = (top+bottom) // 2
            if matrix[row_mid][0] > target:
                bottom = row_mid-1
            elif matrix[row_mid][-1] < target:
                top = row_mid+1
            else:
                break
        
        # 이진탐색 시작할 행을 결정함
        left,right = 0, C-1
        targetRow = matrix[row_mid]
        while left <= right:
            mid = (left+right) // 2
            if targetRow[mid] == target:
                return True
            elif targetRow[mid] > target:
                right = mid-1
            else:
                left = mid+1
        return False