:orphan:

Search a 2D Matrix
==================

.. highlight:: none

Problem
-------
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:**

|image1|

::


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

**Example 2:**

|image2|

::


   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``
- ``-10``\ :sup:```4```\ ``<= matrix[i][j], target <= 10``\ :sup:```4```

.. |image1| image:: https://assets.leetcode.com/uploads/2020/10/05/mat.jpg
.. |image2| image:: https://assets.leetcode.com/uploads/2020/10/05/mat2.jpg

.. highlight:: python

Pattern
-------
Array, Binary Search, Matrix

Approaches
----------

.. tab-set::

    .. tab-item:: Binary Search

        **Code**

        .. literalinclude:: ../problems/medium/search-a-2d-matrix/search_a_2d_matrix__binary_search.py
            :language: python
            :lines: 10-

        **Test**

        >>> from search_a_2d_matrix__binary_search import searchMatrix
        >>> searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3)
        True
        >>> searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13)
        False

        .. autofunction:: search_a_2d_matrix__binary_search.searchMatrix