< Back




74. Search a 2D Matrix

We're given a 2D matrix and asked to determine if a specific number exists or not. We use binary
search in 2 dimensions to accomplish this. Instead of setting the right pointer to the size of one
array, we set the right pointer to m * n - 1 where m is the length of the rows and n is the length of
the columns.

We calculate the middle selection like always, (r + l) // 2, however, when we index into the 2D
matrix, we have to account for it's 2D nature. Thus, for rows we index into matrix[mid // n] and for
columns we index into matrix[mid % n].

With these changes, we conduct our standard binary search and return the result.

The solution is as follows:


  class Solution:
      def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
          m, n = len(matrix), len(matrix[0])
          l, r = 0, m * n - 1

          while l <= r:
              mid = (r + l) // 2
              num = matrix[mid // n][mid % n]

              if num == target:
                  return True

              if num > target:
                  r = mid - 1
              else:
                  l = mid + 1

          return False


_ Time Complexity:

  O(log(mn)) - Standard binary search time complexity.

_ Space Complexity:

  O(1) - Binary search uses constant space.