74. Search a 2D Matrix

[#binary-search, #matrix]

## description

## 74. 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.

Example 1:

plain text

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

plain text

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

–
m == matrix.length
–
n == matrix[i].length
–
1 <= m, n <= 100
–
-104 <= matrix[i][j], target <= 104

Constraints:

## notes

### Intuition

The matrix is sorted both row-wise and column-wise, with each row's first element greater than the previous row's last. First binary search to find the correct row, then binary search within that row.

### Implementation

Use binary search on rows: a row is valid if target ≥ row[0] and target ≤ row[-1]. Once the correct row is found, perform standard binary search within it. If the target isn't in the valid row, return False immediately.

### Edge-cases

If the row-level binary search completes without finding a valid row, return False—don't proceed to the column search.

–
Time: O(log m + log n) — binary search on rows then columns
–
Space: O(1) — only tracking pointers

### Complexity

## solution

python

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        t, b = 0, len(matrix) - 1 # top and bottom
        while t <= b:
            c = (t + b) // 2 # center row
            if target >= matrix[c][0] and target <= matrix[c][-1]:
                l, r = 0, len(matrix[c]) - 1
                while l <= r:
                    m = (l + r) // 2
                    if matrix[c][m] == target:
                        return True
                    elif matrix[c][m] < target:
                        l = m + 1
                    else:
                        r = m - 1
                return False # row that should contain it doesn't
            elif target < matrix[c][0]:
                # row is above, move b
                b = c - 1
            else:
                # row is below, move t
                t = c + 1
        return False
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()

--EOF--