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. 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
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: if not matrix: return False nrow=len(matrix) ncol=len(matrix[0]) length=nrow*ncol l,r=0,length-1 while l<=r: mid=(l+r)>>1 i=mid//ncol j=mid%ncol if matrix[i][j]<target: l=mid+1 elif matrix[i][j]>target: r=mid-1 else: return True return False240. Search a 2D Matrix II
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 in ascending from left to right. Integers in each column are sorted in ascending from top to bottom. Example: Consider the following matrix: [ [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] ] Given target = 5, return true. Given target = 20, return false. class Solution: def searchMatrix(self, matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ if not matrix: return False nrow=len(matrix) ncol=len(matrix[0]) i=0 j=ncol-1 while i<nrow and j>=0: if matrix[i][j]==target: return True elif matrix[i][j]>target: j-=1 else: i+=1 return False