74. Search a 2D Matrix

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

Description: Implement a binary search algorithm to find the target value in a sorted 2D matrix.

Solution:

Firstly, we need to find the row where the target value might be located. We can do this by performing a binary search by comparing the first and last elements of each row with the target value. If the target value is within the range of the row, we can perform another binary search on that row to find the target value.

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

  while (fromRow <= toRow) {
    row = fromRow + Math.floor((toRow - fromRow) / 2)

    if (
      matrix[row][0] <= target &&
      matrix[row][matrix[row].length - 1] >= target
    ) {
      let left = 0
      let right = matrix[row].length - 1

      while (left <= right) {
        const m = left + Math.floor((right - left) / 2)

        if (matrix[row][m] === target) {
          return true
        } else if (matrix[row][m] > target) {
          right = m - 1
        } else {
          left = m + 1
        }
      }
      break
    } else if (matrix[row][0] > target) {
      toRow = row - 1
    } else {
      fromRow = row + 1
    }
  }

  return false
}