Leetcode 240 - Search a 2d matrix II

Note:

  • Use binary search
  • img
  • Matrix is just like BST, we start from top right.
  • When target === m[i][j], we found the result.
  • When target < m[i][j], j-- and we go left.
  • When target < m[i][j], i++ and we go down.

Question:

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

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

Example:

img

1
2
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
const row = matrix.length;
const col = matrix[0].length;
let i = 0, j = col - 1;
while (i < row && j>= 0) {
if (matrix[i][j] === target) return true;
if (matrix[i][j] > target) {
j--;
continue;
} else {
i++;
continue;
}
}
return false;
};