''' Two dimensional array search '''
from typing import List
class Solution:
def find(self, target: int, array:List[List[int]])->int:
''' 1、 Take advantage of the incrementing nature of arrays , Search from the lower left or upper right corner , Take the lower left corner as an example 2、 When target> Matrix elements , Search right , Otherwise, look left 3、 Until you find or the rightmost side of the matrix / At the top Move at most M+N Time ,M For the line ,N Column The time complexity is M+N '''
if len(array) == 0:
return False
rows = len(array) - 1
cols = len(array[0]) - 1
row = rows
col = 0
while row >= 0 and col <= cols:
if target == array[row][col]:
return True
elif target > array[row][col]:
col += 1
else:
row -= 1
return False
def binary_search(self, target, array1d):
left = 0
right = len(array1d) -1
while left <= right:
mid = (left+right)//2
if target < array1d[mid]:
right = mid - 1
elif target > array1d[mid]:
left = mid + 1
else:
return True
return False
def find1(self, target:int, array:List[List[int]])->int:
''' Binary search for each row Time complexity M*log(N) M For the line ,N Column '''
if len(array) == 0:
return False
for i in range(len(array)):
flag = self.binary_search(target, array[i])
if flag:
return True
return flag
if __name__ == "__main__":
solution = Solution()
array = [
[1,2,3,4],
[2,3,4,6],
[3,4,8,9],
[4,7,9,10]
]
print(solution.find(7, array))
print(solution.find1(10, array))
