1. Problem description:
Write an efficient algorithm to search for a target value target in an m x n matrix. This 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 in ascending order from top to bottom.
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]
]
Returns true given target = 5.
Given target = 20, return false.
2. Thought analysis:
① From the title, we can know that the right and downward directions are in ascending order, so it is natural to think of using binary search to solve the problem. We can find the corresponding column in each row, and then find the corresponding column in the column. To see if the element exists, finding elements in rows and columns can be solved by using binary search. We can declare a method, and pass a parameter in the method to indicate whether to search for rows or columns, and then perform binary search.
② Because we can search to the right first, and then search downward, we are faced with these two choices for each element in the matrix, so in addition to using the binary search method, we can also use the recursive method. We can recursively Judging from the method, when the current recursive element is greater than the target, then return directly to the previous layer and try other element values. We can write a recursive method with a return value, as long as it is recursive to the right and recursive to the right. If one is established, it means that the target has been found.
3. The code is as follows:
Binary search:
import sys from typing import List class Solution: def binarySearch(self, l: int, r: int, matrix: List[List[int]], flag: int, x: int, target: int): # binary search column mid = 0 # Set the flag to indicate whether to search in the row or in the column if flag == 0: # Find columns in the same row while l <= r: mid = (l + r) // 2 if matrix[x][mid] == target: return mid elif matrix[x][mid] < target: l = mid + 1 else: r = mid - 1 if matrix[x][mid] > target: return mid - 1 return mid else: # Find rows in the same column mid = 0 while l <= r: mid = (l + r) // 2 if matrix[mid][x] == target: return mid elif matrix[mid][x] < target: l = mid + 1 else: r = mid - 1 return mid def searchMatrix(self, matrix, target): if len(matrix) == 0 or len(matrix[0]) == 0: return False for i in range(len(matrix)): col = self.binarySearch(0, len(matrix[0]) - 1, matrix, 0, i, target) row = self.binarySearch(0, len(matrix) - 1, matrix, 1, col, target) if matrix[row][col] == target: return True return False
Recursive:
import sys from typing import List class Solution: # Matrix rows and columns row, col, max = 0, 0, sys.maxsize """ :param r: the position of the current recursive line :param c: the position of the current recursive column """ def dfs(self, matrix: List[List[int]], target: int, r: int, c: int): if r == self.row or c == self.col: return False if matrix[r][c] == self.max: return False if matrix[r][c] == target: return True if matrix[r][c] > target: return False # Mark visited locations matrix[r][c] = self.max right = self.dfs(matrix, target, r, c + 1) down = self.dfs(matrix, target, r + 1, c) return right or down def searchMatrix(self, matrix, target): if len(matrix) == 0 or len(matrix[0]) == 0: return False self.row, self.col = len(matrix), len(matrix[0]) return self.dfs(matrix, target, 0, 0)