[LeetCode] 74. Search a 2D Matrix

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

Since the given matrix rows are sorted in ascending order, we just flatten the matrix and use binary search to locate the target number.

Time Complexity : O ( Rows * Columns )

Space Complexity :  O ( 1 )

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = len(matrix)
        column = len(matrix[0]) if row > 0 else 0
       
        total = row * column
        
        left, right = 0, total
        
        while left < right:
            mid = left + (right - left) // 2
            
            i = mid // column
            j = mid % column
            
            if matrix[i][j] == target:
                return True
            
            if matrix[i][j] < target:
                left = mid + 1
            else:
                right = mid
        
        return False