# Leetcode 74. Search a 2D Matrix

###### tags: `Leetcode`
---

[link](https://leetcode.com/problems/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:


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

#### Example 2:


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

#### Constraints:

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

---

The provided code implements a binary search algorithm to search for a target value within a 2D matrix. It first checks if the matrix is empty, and if so, returns False.

Then it initializes two pointers, l and r, representing the boundaries of the search range, and enters a while loop to perform binary search. Within each iteration, it calculates the middle index and compares the element at that index with the target value. Based on the comparison, it updates the search range by adjusting the pointers. If the target value is found, it returns True; otherwise, it returns False if the search range is exhausted.

The algorithm assumes that the matrix is sorted in row-wise and column-wise order, and its time complexity is O(log(n * m)), where n and m are the dimensions of the matrix.

#### Solution 1

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = len(matrix)
        if row == 0:
            return False

        col = len(matrix[0])
        if col == 0:
            return False

        l, r = 0, (row * col) - 1
        while l <= r:
            mid = (l + r) // 2
            i = mid // col
            j = mid % col
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                r = mid - 1
            else:
                l = mid + 1

        return False
        

O(T): O(log(n * m))
O(S): O(1)