In an N by m two-dimensional array, each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Perform an efficient function that takes such a two-dimensional array and an integer and determines whether the integer is in the array.

Example:

The existing matrix matrix is as follows:

[[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]]Copy the code

Given target = 5, return true. Given target = 20, return false.

Limit: 0 <= N <= 1000 0 <= m <= 1000

solution

The number in the upper right is the maximum value of the row, the minimum value of the column. Compare target with the number. If target is large, the number row is excluded. If target is small, the number column is excluded.

var findNumberIn2DArray = function(matrix, target) { if(matrix.length == 0 || matrix[0].length == 0) return false var rows = matrix.length var cols = Matrix [0].length // define the initial coordinates var row = 0 var col = cols-1 while(row < rows && col >= 0){// define the range if(matrix[row][col] == Target){return true}else if(matrix[row][col] > target){col-- // remove column}else{row++ // remove line}} return false};Copy the code