Topic describes

Write an efficient algorithm to search a target value in m x n matrix matrix. The matrix has the following properties: the elements of each row are arranged in ascending order from left to right. The elements of each column are arranged from top to bottom.

Example 1:

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 = 5Output:true
Copy the code

Example 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 = 20Output:false

Copy the code

Thought analysis

  1. My idea is: since each row and each column are sorted, let’s do the dichotomy line by line, and I don’t know how to calculate the time, so it’s less than O(n^2). Of course, the time complexity of this method is still very high. After reading the solution, I know that there is a simpler and less time complexity algorithm
  2. This algorithm makes full use of the characteristics of the two-dimensional matrix, starting from the lower left corner of the two-dimensional matrix traversal up and right, the top of the point is smaller than the value, the right side of the point is larger than the value, so you can perform shear traversal, reduce the array line by line. For example, if the target value is 8 and the bottom-left corner value is 18, then the target value is smaller than that value because 18 is greater than 8, so move up one line. After doing this, if the array length is exceeded, there is no target value, otherwise it can be found.

AC code

Each row of binary

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  let y = 0
  while (y < matrix.length) {
    let min = 0, max = matrix[0].length - 1
    while (min <= max) {
      let mid = parseInt((min + max) / 2)
      if (matrix[y][mid] === target) {
        return true
      }
      else if (matrix[y][mid] > target) {
        max = mid - 1
      }
      else {
        min = mid + 1
      }
    }
    y++
  }
  return false
};
Copy the code

Cutting method

/ * * *@param {number[][]} matrix
 * @param {number} target
 * @return {boolean}* /
var searchMatrix = function (matrix, target) {
  let n = matrix.length - 1
  let m = 0
  while(m<matrix[0].length&&n >=0) {
    if(matrix[n][m]>target){
      n--
    }
    else if(matrix[n][m]<target) {
      m++
    }
    else {
      return true}}return false
};
Copy the code

conclusion

As you can see from this problem, the algorithm has a lot to do with mathematics