search_a_2d_matrix
1# @leet start 2class Solution: 3 def searchMatrix(self, matrix: list[list[int]], target: int) -> bool: 4 """ 5 This problem asks to to search in a 2D matrix where each row is sorted 6 in non-decreasing order and the first integer of every row is greater 7 then the last integer of the previous row. 8 9 The brute force would be $O(m * n)$ time, where you search every cell for 10 the value. 11 12 However, the question asks for a solution in $O(\log{}m * n)$ time. 13 To do so, we can binary search to find the row that could contain the value 14 and then binary search inside that row to check if the value exists. 15 16 This can be expressed a bit more tersely by using a bisect function. 17 """ 18 left, right = 0, len(matrix) - 1 19 20 row_idx = None 21 22 while left <= right: 23 mid = (left + right) // 2 24 if matrix[mid][0] <= target <= matrix[mid][-1]: 25 row_idx = mid 26 break 27 elif matrix[mid][-1] < target: 28 left = mid + 1 29 else: 30 right = mid - 1 31 32 if row_idx is None: 33 return False 34 35 row = matrix[row_idx] 36 37 left, right = 0, len(row) - 1 38 while left <= right: 39 mid = (left + right) // 2 40 if row[mid] == target: 41 return True 42 elif row[mid] < target: 43 left = mid + 1 44 else: 45 right = mid - 1 46 47 return False 48 49 50# @leet end 51sol = Solution() 52 53 54def test(): 55 assert sol.searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3) 56 assert not sol.searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13)
class
Solution:
3class Solution: 4 def searchMatrix(self, matrix: list[list[int]], target: int) -> bool: 5 """ 6 This problem asks to to search in a 2D matrix where each row is sorted 7 in non-decreasing order and the first integer of every row is greater 8 then the last integer of the previous row. 9 10 The brute force would be $O(m * n)$ time, where you search every cell for 11 the value. 12 13 However, the question asks for a solution in $O(\log{}m * n)$ time. 14 To do so, we can binary search to find the row that could contain the value 15 and then binary search inside that row to check if the value exists. 16 17 This can be expressed a bit more tersely by using a bisect function. 18 """ 19 left, right = 0, len(matrix) - 1 20 21 row_idx = None 22 23 while left <= right: 24 mid = (left + right) // 2 25 if matrix[mid][0] <= target <= matrix[mid][-1]: 26 row_idx = mid 27 break 28 elif matrix[mid][-1] < target: 29 left = mid + 1 30 else: 31 right = mid - 1 32 33 if row_idx is None: 34 return False 35 36 row = matrix[row_idx] 37 38 left, right = 0, len(row) - 1 39 while left <= right: 40 mid = (left + right) // 2 41 if row[mid] == target: 42 return True 43 elif row[mid] < target: 44 left = mid + 1 45 else: 46 right = mid - 1 47 48 return False
def
searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
4 def searchMatrix(self, matrix: list[list[int]], target: int) -> bool: 5 """ 6 This problem asks to to search in a 2D matrix where each row is sorted 7 in non-decreasing order and the first integer of every row is greater 8 then the last integer of the previous row. 9 10 The brute force would be $O(m * n)$ time, where you search every cell for 11 the value. 12 13 However, the question asks for a solution in $O(\log{}m * n)$ time. 14 To do so, we can binary search to find the row that could contain the value 15 and then binary search inside that row to check if the value exists. 16 17 This can be expressed a bit more tersely by using a bisect function. 18 """ 19 left, right = 0, len(matrix) - 1 20 21 row_idx = None 22 23 while left <= right: 24 mid = (left + right) // 2 25 if matrix[mid][0] <= target <= matrix[mid][-1]: 26 row_idx = mid 27 break 28 elif matrix[mid][-1] < target: 29 left = mid + 1 30 else: 31 right = mid - 1 32 33 if row_idx is None: 34 return False 35 36 row = matrix[row_idx] 37 38 left, right = 0, len(row) - 1 39 while left <= right: 40 mid = (left + right) // 2 41 if row[mid] == target: 42 return True 43 elif row[mid] < target: 44 left = mid + 1 45 else: 46 right = mid - 1 47 48 return False
This problem asks to to search in a 2D matrix where each row is sorted in non-decreasing order and the first integer of every row is greater then the last integer of the previous row.
The brute force would be $O(m * n)$ time, where you search every cell for the value.
However, the question asks for a solution in $O(\log{}m * n)$ time. To do so, we can binary search to find the row that could contain the value and then binary search inside that row to check if the value exists.
This can be expressed a bit more tersely by using a bisect function.
sol =
<Solution object>
def
test():