Topic describes

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.

The subject sample

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.

Subject analysis

The given data is a two-dimensional array. One method is to iterate through the array and return true if the corresponding target is found, or false if not. The second method is linear search, based on the two-dimensional array row and column search, detailed steps are as follows:

  • For example, find the last element in the first row and compare it to target. If it is larger than target, the index of the corresponding column is reduced by one
  • If the element is smaller than target, the index for the column stays the same, and the index for the row increases by one, because the data is incrementing. If the last data in the current row is smaller than taget, then all previous data will be smaller than Target
  • Returns true if equal

Code implementation

/ * * *@param {number[][]} matrix
 * @param {number} target
 * @return {boolean}* /
var findNumberIn2DArray = function(matrix, target) {
    // Check the boundary value, if not, return false
    if (matrix == null || matrix.length === 0 || matrix[0].length === 0) {
        return false
    }
    let rowIndex = 0; / / the first line
    let colIndex = matrix[rowIndex].length - 1; // First row and last column
    // The row index cannot exceed the length of the array. Similarly, the column index cannot be negative because it does not exist
    while(rowIndex <= matrix.length - 1 && colIndex >= 0) {
        if (matrix[rowIndex][colIndex] < target) {
            rowIndex++
        } else if (matrix[rowIndex][colIndex] > target) {
            colIndex--
        } else if (matrix[rowIndex][colIndex] === target){
            return true}}return false
};
Copy the code

Title source

LeetCode: Reference to Offer 04. Lookup in a two-dimensional array