Given a Matrix of size n*n and an element E to search in the Matrix. Each row and each column of the Matrix is sorted. We need to find an efficient algorithm to search this matrix.
Solution:
Take the last element of the first row and go either down or left using the following logic:
1. If the search element E is greater than the current element go down one step. i.e change the row to the next row.
2. If the search element E is less than the current element then go one step to the left. i.e change the col = col - 1.
Do the above operation till u find the element E or you have reached the end of the Matrix. End of the Matrix means we cannot move either to left or down.
Runtime of the algorithm would be around O(n).
8 comments:
I think we can use the Binary Search approach along the two directions (Rows & Columns)to speed up the algorithm further.
After each iteration(row & column), the size of the sub matrix(to be searched) will keep reducing by 1/4th.
Binary search can also be used but this is the fastest of both i believe.
I think if we Use Binary Search in two direction we could end up with the complexity of (log(n)*log(n)).!
it will take O(logn)(not logn*logn) time, where nxn is the size of matrix.
With each operation, size of matrix will be reduced to n/2 x n/2.
1) divide matrix into 4 parts,
2) with caomparisons(fixed no.), u could point out exact quadrant, where the being searched no. will lie.
3) repeat 1 and 2, untill solution found.
Hi ashish...can u explain how your step 2 works?
dude my code was not that clean, Actually simple thing is, there are nine pts when u divide a square into 4 parts.
a------b------c
'-------'-------'
'-------'-------'
'-------'-------'
d------e------f
'-------'-------'
'-------'-------'
'-------'-------'
g------h------i
worst case comparing with these 9 pts u can precisely point out exact quadrant where a element lies.
Better solution would be to move along the diagonal.thereby reducing the no of comparisons to be made...
Post a Comment