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.
For 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.
Solution:
1. 1st idea use one binary search
iterate every rows , binary search from row i to find the insertion position p (bisect_right)
m = len(matrix), n = len(matrix[0]) time complexity O(m*logn)
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
i = 0
while (i < len(matrix)):
pos = bisect_right(matrix[i], target) #use binary search
#print(" aaas: ",i, pos-1)
if matrix[i][pos-1] == target:
return True
i += 1
return False
2. 2nd utilize the ordered row and column, start from bottom left value v, if v is bigger than target, then go the upper column, else go the right row. time complexity o(m+n)
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
m = len(matrix)
n = len(matrix[0])
i = m-1 #row
j = 0 #column
while ( i >= 0 and j <= n-1):
if matrix[i][j] == target:
return True
elif matrix[i][j] > target:
i -= 1
else:
j += 1
return False
3. we can also use divide and conquer:
reference: