Topic describes

Search for a two-dimensional matrix

Write an efficient algorithm to determine whether there is a target value in an M x n matrix. The matrix has the following characteristics:

The integers in each row are arranged in ascending order from left to right. The first integer in each line is greater than the last integer in the previous line.

The sample

Input: matrix = [[1.3.5.7], [10.11.16.20], [23.30.34.60]], target = 3Output:true
Copy the code
Input: matrix = [[1.3.5.7], [10.11.16.20], [23.30.34.60]], target = 13Output:false
Copy the code

answer

Generally speaking, once you see an ordered word in a problem, your first reaction should be to think of binary search. Here is a common binary search template for the author:

function binarySearch(arr, target) {
  let start = 0,
    end = arr.length - 1,
    mid
  while (start <= end) {
    mid = Math.floor(start + (end - start) / 2)
    if (arr[mid] > target) {
      end = mid - 1
    } else if (arr[mid] < target) {
      start = mid + 1
    } else {
      return true}}return false
}
Copy the code

According to the specific requirements of the topic template to modify the corresponding conditions, the problem is solved.

Method a

Back to the problem, the first idea that comes to my mind is to use binary search method to find the possible row of the target value according to the first item of each group, that is, to define a function searchRow, input a two-dimensional matrix and the target value, and return the possible row of the target value. Start from the middle. If the first number in the middle row is greater than the target value, the second half and this row are not considered. If the first number in the middle row is less than or equal to the target value, the first half is not considered.

var searchRow = function (matrix, target) {
  var start = -1,
    end = matrix.length - 1,
    mid
  while (start < end) {
    var mid = Math.floor((end - start + 1) / 2) + start
    if (matrix[mid][0] <= target) {
      start = mid
    } else if (matrix[mid][0] > target) {
      end = mid - 1}}return start
}
Copy the code

After finding the possible position of the target value, the problem is reduced to searching in a one-dimensional sequential matrix. The standard binary search method can be used:

var searchCol = function (arr, target) {
  var start = 0,
    end = arr.length - 1,
    mid
  while (start <= end) {
    mid = Math.floor(start + (end - start) / 2)
    if (arr[mid] === target) {
      return true
    } else if (arr[mid] > target) {
      end = mid - 1
    } else {
      start = mid + 1}}return false
}
Copy the code

The complete code is as follows:

var searchMatrix = function (matrix, target) {
  const rowIndex = searchRow(matrix, target)
  if (rowIndex < 0) {
    return false
  }
  return searchCol(matrix[rowIndex], target)
}

var searchRow = function (matrix, target) {
  var start = -1,
    end = matrix.length - 1,
    mid
  while (start < end) {
    var mid = Math.floor((end - start + 1) / 2) + start
    if (matrix[mid][0] <= target) {
      start = mid
    } else if (matrix[mid][0] > target) {
      end = mid - 1}}return start
}

var searchCol = function (arr, target) {
  var start = 0,
    end = arr.length - 1,
    mid
  while (start <= end) {
    mid = Math.floor(start + (end - start) / 2)
    if (arr[mid] === target) {
      return true
    } else if (arr[mid] > target) {
      end = mid - 1
    } else {
      start = mid + 1}}return false
}
Copy the code

Complexity analysis:

  • Time complexity: O(log(mn)), where M and n are the number of rows and columns of the matrix respectively
  • Space complexity: O(1), only constant temporary variables are used

Method 2

Because the numbers in this matrix have a special arrangement order, the two-dimensional matrix will be an ascending one-dimensional array after being flattened, so using the subscript mapping relationship between the row number and column number of the two-dimensional matrix and the one-dimensional matrix, we can completely treat this problem as an ascending one-dimensional matrix directly and use the dichotomy template to solve the problem.

Here is the subscript mapping technique for one-dimensional and two-dimensional matrices. Suppose we have such a two-dimensional matrix:

1  3  5  7
10 11 16 20
20 30 34 50
Copy the code

For example, the number 16 in row 2 and column 3, whose matrix coordinate is (2, 1), is mapped to a one-dimensional array, and its corresponding subscript index idx=6

idx=6=i*n+j=1*4+2=6
Copy the code

So how do I get the coordinates of the matrix backwards by idx=6?

i=idx/n=6/4 =1
j=idx%n=6%4 =2
Copy the code

The coordinates of the matrix are (I,j) ==>(1,2).

Back to the problem, we treat two-dimensional matrix as one-dimensional matrix to solve the problem. First, we define a subscript mapping method mapCoord:

var mapCoord = function (index, itemLength) {
  const row = Math.floor(index / itemLength)
  const col = index % itemLength
  return { row, col }
}
Copy the code

Then apply the template:

var searchMatrix = function (matrix, target) {
  if (matrix.length === 0 || matrix[0].length === 0) return false
  var start = 0,
    end = matrix.length * matrix[0].length - 1,
    mid,
    midCoord
  while (start <= end) {
    mid = Math.floor(start + (end - start) / 2)
    midCoord = mapCoord(mid, matrix[0].length)
    if (matrix[midCoord.row][midCoord.col] > target) {
      end = mid - 1
    } else if (matrix[midCoord.row][midCoord.col] < target) {
      start = mid + 1
    } else {
      return true}}return false
}
Copy the code

Does it feel easier?

Complexity analysis:

  • Time complexity: O(log(mn)), where M and n are the number of rows and columns of the matrix respectively
  • Space complexity: O(1), only constant temporary variables are used

Refer to the link

Common conversion techniques for two-dimensional matrices