Search
for an element in an nxm matrix in which the elements in the rows and
columns individually sorted in ascending order.
Eg:
1 2 3 9
4 5 6 12
7 8 11 22
10 18 30 35
Consider
a sorted matrix and a 'key' to search. Start by comparing the key
with the last element in the first row. If it is the element we are
searching for, we are done. Otherwise, continue to search by
eliminating either a row or a column on each comparison. The
algorithm stops when either we have found the element or do not have
any more elements to compare, in which case the 'key' is not in the
matrix.
Here
is a step-by-step process to search for an element '7' in the matrix
above.
Step
1: Compare with 9. Eliminate the current column and move left as 7 <
9.
|
1
|
2
|
3
|
9
|
|
4
|
5
|
6
|
12
|
|
7
|
8
|
11
|
22
|
|
10
|
18
|
30
|
35
|
Step
2: Compare with 3. Eliminate the current row and move down as 7 >
3.
|
1
|
2
|
3
|
9
|
|
4
|
5
|
6
|
12
|
|
7
|
8
|
11
|
22
|
|
10
|
18
|
30
|
35
|
Step
3: Compare with 6. Eliminate the current row and move down as 7 >
3.
|
1
|
2
|
3
|
9
|
|
4
|
5
|
6
|
12
|
|
7
|
8
|
11
|
22
|
|
10
|
18
|
30
|
35
|
Step
4: Compare with 11. Eliminate the current column and move left as 7 <
11.
|
1
|
2
|
3
|
9
|
|
4
|
5
|
6
|
12
|
|
7
|
8
|
11
|
22
|
|
10
|
18
|
30
|
35
|
Step
5: Compare with 8. Eliminate the current column and move left as 7 <
8
|
1
|
2
|
3
|
9
|
|
4
|
5
|
6
|
12
|
|
7
|
8
|
11
|
22
|
|
10
|
18
|
30
|
35
|
Step
6: Compare with 7. Print the position and stop.
|
1
|
2
|
3
|
9
|
|
4
|
5
|
6
|
12
|
|
7
|
8
|
11
|
22
|
|
10
|
18
|
30
|
35
|
Here
is the C++ code for this algorithm:
int
sorted_matrix[4][4] = { {1,2,3,9}, {4,5,6,12}, {7,8,11,22},
{10,18,30,35} };
bool
FindInSortedMatrix(int
key, int
row_size, int
col_size) {
int
row = 0, col = col_size; //start at the
first row, last column
while(row
<= row_size && col >= 0) {
if(sorted_matrix[row][col]
== key) { //key found
cout
<< "Found at "
<< row << " "
<< col << endl;
return
true;
}
else
if(sorted_matrix[row][col]
> key) {
--col;
//eliminate this column
}
else
{
++row;
//eliminate this row
}
}
return
false;
//no more elements to compare
}
To
find the element 7, invoke the function as:
FindInSortedMatrix(7,3,3);
In
the best case, only one comparison has to be performed, which takes
O(1) time. In the worst case, we will have to compare the key with
all the elements in the last column and all the elements in the last
row. The complexity in this case is O(row_size + col_size). If it is
a square matrix, the complexity is O(row_size), as row_size =
col_size in this case.
This
approach is simple. A divide-and-conquer approach can be used to get
a more efficient solution. I'll discuss it in a future post.
No comments:
Post a Comment