2d-search.js

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
  if (matrix.length === 0) return false
  let filteredRows = getFilteredRows(matrix, target)
  let filteredCols = getFilteredCols(matrix, target)
  for (let row of filteredRows) {
    if (search(matrix[row], filteredCols, target) > -1) return true
  }
  return false
};

function search(arr, indices, target) {
  let lo = 0
  let hi = indices.length - 1
  while (lo <= hi) {
    let mid = lo + Math.floor((hi - lo) / 2)
    if (target < arr[indices[mid]]) hi = mid - 1
    else if (target > arr[indices[mid]]) lo = mid + 1
    else return mid
  }
  return -1
}

function getFilteredRows(matrix, target) {
  let result = []
  let numCols = matrix[0].length
  for (let i = 0; i < matrix.length; i++) {
    if (
      matrix[i][0] <= target &&
      matrix[i][numCols - 1] >= target
    ) {
      result.push(i)
    }
  }
  return result
}

function getFilteredCols(matrix, target) {
  let result = []
  let numRows = matrix.length
  for (let i = 0; i < matrix[0].length; i++) {
    if (
      matrix[0][i] <= target &&
      matrix[numRows - 1][i] >= target
    ) {
      result.push(i)
    }
  }
  return result
}