Leetcode 74 Search a 2D Matrix
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.
- Eklenecek.
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
ROWS,COLS = len(matrix),len(matrix[0])
top,bot = 0, ROWS - 1
while top <= bot:
row = (top+bot)//2
if target > matrix[row][-1]:
top = row + 1
elif target < matrix[row][0]:
bot = row -1
else:
break
if not(top<=bot):
return False
row = (top + bot) // 2
l,r = 0, COLS - 1
while l <= r:
m = (l+r)//2
if target > matrix[row][m]:
l = m + 1
elif target < matrix[row][m]:
r = m - 1
else:
return True
return False