Search_a_2D_Matrix.js

/*
Search a 2D Matrix
https://leetcode.com/problems/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
*/
const assert = require('assert');

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
  if(matrix.length === 0)
    return false;
  return searchMatrixAux(matrix, 0, matrix.length - 1, target);
};

var searchMatrixAux = function(matrix, firstRow, lastRow, target) {
  if(firstRow === lastRow) {
    var iter = 0; 
    while(iter < matrix[0].length) {
      if(matrix[firstRow][iter] === target)
        return true;
      iter++;
    }
  } else {
    var middle = Math.floor((firstRow + lastRow) / 2); // 0
    if(target > matrix[middle][matrix[0].length - 1]) 
      return searchMatrixAux(matrix, middle + 1, lastRow, target)
    else 
      return searchMatrixAux(matrix, firstRow, middle, target)
  }
  
  return false;
};
 
var main = function(){
  test();
}

var test = function(n) {
  assert.equal(searchMatrix([], 0), false);
  assert.equal(searchMatrix([[1], [3]], 3), true);
  assert.equal(searchMatrix([[1], [3]], 1), true);
  const matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]];
  assert.equal(searchMatrix(matrix, 3), true);
}

module.exports.main = main;