Search a 2D Matrix

Description

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

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

Example 2:

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

Solution(javascript)

const searchMatrix = (matrix = [], target) => {
  if (matrix.length === 0) {
    return false
  }
  const rowLength = matrix.length
  const columnLength = matrix[0].length
  const getMiddleIndex = n => [Math.floor(n / columnLength), n % columnLength]
  let low = 0
  let high = rowLength * columnLength - 1
  while (low <= high) {
    const middle = Math.floor((low + high) / 2)
    const [rowIndex, columnIndex] = getMiddleIndex(middle)
    const current = matrix[rowIndex][columnIndex]
    if (current === target) {
      return true
    }
    if (current < target) {
      low = middle + 1
    } else {
      high = middle - 1
    }
  }
  return false
}