240 Search a 2D Matrix II – Medium¶
Problem:¶
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 = 20, return false.
Thoughts:¶
For version one, Search a 2D Matrix, basic idea is to leverage binary search. Since it’s a 2D matrix, then use a 2x binary search can solve the problem. So for this one, because it’s not the same order as the version I, so we need to check more elements to find the target element if we want to use a 2x binary search.
However, just like the version I, we can do a one binary search by considering the 2D array as 1D array. For this problem, we can notice a property, say for the below example.
[
[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]
]
Also remember to return false, if index is out of bound indicating not found target element.