noodleProblems/
Search a 2D Matrix
#81

Search a 2D Matrix

AlgorithmmediumArrayBinary SearchMatrix

You are given an m x n integer matrix with two properties: - Each row is sorted in non-decreasing order from left to right. - The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if it appears in the matrix, and false otherwise. Aim for O(log(m·n)) time.

Example cases

  • present
    in matrix =
    1357
    10111620
    23303460
    target = 3
    out true
    3 is in the first row.
  • absent
    in matrix =
    1357
    10111620
    23303460
    target = 13
    out false
    13 falls in the gap between rows.
  • single cell hit
    in matrix =
    5
    target = 5
    out true

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -10^4 <= matrix[i][j], target <= 10^4
Saved
matrix =
[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
target =
3