Given m x n matrix that 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.
Write an efficient algorithm that searches for a value in this matrix. For example, consider the following matrix:[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
Given target =
true. Else, return
Since the integers are sorted left to right and the last integer on the current row is always less than the first integer on the next row, we can treat this as a “normal” sorted array and perform binary search with some tricks.
- Likewise, init the two pointers
leftwith 0 and
right with m*n-1, where m is length of columns and n is length of rows
- Perform the usual binary search: find the middle value and cut the invariant half depending on greater or less than target. But, this time use the mid/n to select the row integer and mid%n to select the column integer
The complete code would be as below:
def search(matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ row, col = len(matrix), len(matrix) l, r = 0, row*col-1 while l<=r: mid = (l+r)/2 num = matrix[mid/col][mid%col] if num == target: return True if num > target: r = mid-1 else: l = mid+1 return False