LC 0074 [M] Search a 2D Matrix - ALawliet/algorithms GitHub Wiki

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int):
        ROWS = len(matrix)
        COLS = len(matrix[0])
        
        lo = 0
        hi = ROWS*COLS - 1
        while lo <= hi:
            m = (lo + hi) // 2
            # r = m // COLS
            # c = m % COLS
            r, c = divmod(m, COLS)
            
            if target == matrix[r][c]:
                return True
            elif target > matrix[r][c]:
                lo = m + 1
            elif target < matrix[r][c]:
                hi = m - 1
                
        return False

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        r = bisect_left(matrix, target, key=lambda row: row[-1])  # or key=itemgetter(-1) search for row
        if r >= len(matrix): return False
        c = bisect_left(matrix[r], target) # search for column
        return matrix[r][c] == target

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        r = bisect_left(matrix, target, key=lambda row: row[-1])  # or key=itemgetter(-1) search for row
        return r < len(matrix) and matrix[r][bisect_left(matrix[r], target)] == target # search for column

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS = len(matrix)
        COLS = len(matrix[0])
        def get(idx):
            r, c = divmod(idx, COLS)
            return matrix[r][c]
        return get(bisect_left(range(ROWS*COLS-1), target, key=get)) == target

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS, COLS = len(matrix), len(matrix[0])
        
        # binary search to find the row
        top, bot = 0, ROWS - 1
        while top <= bot:
            row = (top + bot) // 2 # middle row
            if target > matrix[row][-1]:
                top = row + 1
            elif target < matrix[row][0]:
                bot = row - 1
            else:
                break
                
        if not (top <= bot):
            return False
        
        # binary search within the row
        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(m*n))