# 240 Searching a 2D matrix II (recursion, binary search)

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: return False
for i in range(len(matrix)):
col = self.binarySearch(0, len(matrix) - 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: return False
self.row, self.col = len(matrix), len(matrix)
return self.dfs(matrix, target, 0, 0)
```

Posted by phpnewbie1979 on Wed, 18 May 2022 14:26:28 +0300