Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. Example 1:
Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 Output: true Example 2:
Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 Output: false
My code:
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
#LOG2N algorithm
#first finding the
if len(matrix)==0:
return False
example=matrix[0]
if len(example)==0:
return False
index_row=self.search_row(matrix,0,len(matrix)-1,target)
if index_row==-1:
return False
example=matrix[index_row]
print(example)
label=self.search_column(example,0,len(example)-1,target)
return label
def search_row(self,matrix,i,j,target):
if j-i<=2:
check_index=-1
for k in range(i,j+1):
if matrix[k][0]<=target:
check_index=k
return check_index
mid=int((i+j)/2)
if target>matrix[mid][0]:
return self.search_row(matrix,mid,j,target)
else:
return self.search_row(matrix,i,mid,target)
def search_column(self,example,i,j,target):
if j-i<=2:
check_index=-1
for k in range(i,j+1):
if example[k]==target:
check_index=k
if check_index==-1:
return False
return True
mid=int((i+j)/2)
if target>example[mid]:
return self.search_column(example,mid,j,target)
else:
return self.search_column(example,i,mid,target)