Search in a 2D Array or Matrix - Algorithms and Problem SolvingAlgorithms and Problem Solving
Search in a 2D Array or Matrix
Write an efficient algorithm that searches for a value in an m x n matrix.
Matrix can have two forms. Solve it for each form of the matrix. This matrix has the following properties:
Version 1
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.
For example,
[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]
Then,
search(mat, 11) = true
search(mat, 2) = false
search(mat, 17) = false
Version 2
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,
[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]
Then,
search(mat, 11) = true
search(mat, 3) = false
search(mat, 17) = true
version 1 : First element is greater then last element of previous row
At each row we can know in O(lgn) time if the desired element is there or not. But which row to look into. As the rows are wrapped around in sorted order so, we can easily find the row which may contain the target. So, we will do a vertical binary search over first column to identify the row.
1. If the mid is greater than the key than we know that this row and all next rows do not contain the mid. So, search upward. 2. On the other hand if mid is less than the key than either this row may contain the key or all subsequent rows.
Now, we found a candidate row. We now do normal horizontal binary search in that row to search the key. Below is implementation of this idea which simply runs in O(lgn) time .
Read full article from Search in a 2D Array or Matrix - Algorithms and Problem SolvingAlgorithms and Problem Solving
No comments:
Post a Comment