# [Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/)
###### tags: `Leetcode`, `Medium`, `Binary Search`

## Approach

* The numbers on each row are arranged in ascending order. The first number of the next row is greater than the last number of the previous row. This makes it easy to apply binary search technique to this problem.
* Take the `mid_row` and check if the target is in the range of the numbers in that row.
* If it is, then take the mid element of this row and apply the binary search technique on this row. If the target element is found, return True. Otherwise, return False
* If the target element is less than the first element of the `mid_row`, then apply the binary search technique to identify the row range before the mid_row and continue to find the target.
* If the target element is greater than the last element of the `mid_row`, then apply the binary search technique to identify the row range after the mid_row and continue to find the target.

## Asymptotic Analysis
### Time Complexity: **O(log(MN))**
### Space Complexity: **O(1)**

## Code

from typing import List


class Search2DMatrix:
    def search_matrix(self, matrix: List[List[int]], target: int) -> bool:
        r_left, r_right = 0, len(matrix) - 1
        while r_left <= r_right:
            r_mid = (r_right + r_left) // 2
            row = matrix[r_mid]
            last_element = len(matrix[r_mid]) - 1
            if row[last_element] >= target >= row[0]:
                c_left, c_right = 0, last_element
                while c_left <= c_right:
                    c_mid = (c_right + c_left) // 2
                    if target == row[c_mid]:
                        return True
                    elif target > row[c_mid]:
                        c_left = c_mid + 1
                    else:
                        c_right = c_mid - 1
                return False
            elif target > row[last_element]:
                r_left = r_mid + 1
            elif target < row[0]:
                r_right = r_mid - 1
        return False


nums_matrix, target_num = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13
print("Searching for " +
      str(target_num) +
      " in the matrix: " +
      str(Search2DMatrix().search_matrix(nums_matrix, target_num)))