LC 74. Search a 2D Matrix

The problem

Solution $O(\log (m * n))$

Given a matrix sorted like a 1-dimensional array, this can be solved with a regular binary search. The only twist is being creative about calculating the row and column indices. Treating the matrix like a flat, with indices 1 to n, there are to formulas that will always provide the row and column.

Considering a 3 x 3 matrix, if the imaginary flattened index, mid, is 5, then the row would be $\lfloor5 / 3\rfloor = 1$ (the weird brackets are the math proof notation for Math.floor()) and the column would be $5 \bmod 3 = 2$. Therefore, the 5th overall element is the 3rd element of the 2nd row. Notice that the division for each is the same. Mathematically, the quotient, or whole number portion of the division pulled out by Math.floor is the row index, and the remainder pulled out by % is the column index.

function searchMatrix(matrix: number[][], target: number): boolean {
  let numberOfCols = matrix[0].length
  let left = 0
  let right = matrix.length * matrix[0].length - 1
  while (left <= right) {
    const mid = Math.floor((right + left) / 2)
    const rowIdx = Math.floor(mid / numberOfCols) // Gets quotient of division
    const colIdx = mid % numberOfCols // Gets remainder of division
    const midValue = matrix[rowIdx][colIdx]
    if (midValue === target) {
      return true
    } else if (midValue > target) {
      right = mid - 1
    } else if (midValue < target) {
      left = mid + 1
    }
  }

  return false
}