# Search a 2D Matrix

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

``````/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
* @time complexity: O(log(nm))
* @space complexity: O(1)
*/
var searchMatrix = function(matrix, target) {
if (matrix.length === 0) {
return false;
}

const m = matrix.length;
const n = matrix[0].length;

let left = 0;
let right = m * n - 1;

while (left <= right)="" {="" const="" midindex="Math.floor((left" +="" 2);="" midvalue="matrix[Math.floor(midIndex" n)][midindex="" %="" n];="" if="" (midvalue="==" target)="" return="" true;="" }="" <="" left="midIndex" 1;="" else="" right="midIndex" -="" false;="" code="">``````

### Test Case

``````const assert = require('chai').assert;

describe('Search a 2D Matrix', () => {

it('should return true', () => {
const matrix = [
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
];
assert.strictEqual(searchMatrix(matrix, 3), true);
});

it('should return false', () => {
const matrix = [
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
];
assert.strictEqual(searchMatrix(matrix, 13), false);
});

});
``````
``````
Search a 2D Matrix
✓ should return true
✓ should return false

2 passing (11ms)
``````

Mike Mai   Brooklyn, New York
I am full-stack web developer, passionate about building world class web applications. Knowledge in designing, coding, testing, and debugging. I love to solve problems.