BST: 74. Search a 2D Matrix ★★★

74. Search a 2D Matrix

 

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

        l, r = 0, COLS*ROWS - 1

        while l<=r:
            mid = (l+r)//2

            rr = mid // COLS
            cc = mid % COLS

            if matrix[rr][cc] < target:
                l = mid+1
            elif matrix[rr][cc] > target:
                r = mid-1
            else:
                return True

        return False

 

https://youtu.be/Ber2pi2C0j0

 

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        def bst(arr, t):
            l, r = 0, len(arr)-1

            while(l<=r):
                m = (l+r)//2
				"""
                아래 부분.. 주의!!.. 자주 틀림!!                
                if arr[m] < t:
                    l = m+1
                elif t < arr[m]:
                    r = m-1
                """
                if arr[m] < t:
                    l = m+1
                elif t < arr[m]:
                    r = m-1
                else:
                    return True
            return False
        
        for mm in matrix:
            if mm[0] <= target and target <= mm[-1]:
                 ck = bst(mm, target)
                 if ck == True:
                    return True
        return False

 

최종 코드

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

        left, right=0, rows*cols-1

        while left<=right:
            m = (left+right)//2

            r = m // cols
            c = m % cols

            if matrix[r][c] < target:
                # 커져야 함
                left = m+1
            elif matrix[r][c] > target:
                # 작아져야 함
                right = m-1
            else:
                return True
        return False