Skip to content

74. Search a 2D Matrix

https://leetcode.com/problems/search-a-2d-matrix/

js
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
  var l = 0
  var r = matrix.length - 1

  while (l <= r) {
    let mid = (l + r) / 2 >> 0
    if (matrix[mid][0] === target) {
      return true
    } else if (matrix[mid][0] < target) {
      l = mid + 1
    } else {
      r = mid - 1
    }
  }

  if (r < 0) {
    return false
  }

  var row = r
  l = 0
  r = matrix[0].length - 1

  while (l <= r) {
    let mid = (l + r) / 2 >> 0
    if (matrix[row][mid] === target) {
      return true
    } else if (matrix[row][mid] < target) {
      l = mid + 1
    } else {
      r = mid - 1
    }
  }

  return false
}
py
class Solution(object):

    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        l, r = 0, len(matrix) - 1

        while l <= r:
            mid = (l + r) // 2
            if matrix[mid][0] == target:
                return True
            elif matrix[mid][0] < target:
                l = mid + 1
            else:
                r = mid - 1

        if r < 0:
            return False

        row, l, r = r, 0, len(matrix[0]) - 1

        while l <= r:
            mid = (l + r) // 2
            if matrix[row][mid] == target:
                return True
            elif matrix[row][mid] < target:
                l = mid + 1
            else:
                r = mid - 1

        return False