Programming Challenge 3 at Dev102.com is to find an element in a mxn matrix whose rows and columns are sorted in ascending order. A quick and easy way to do this is to perform a binary search in the first column to find the row with the highest value that is less than or equal to the value for which you're searching. Then, perform a binary search in that row to find the element.
If that didn't find the element, then do the same thing except perform the binary search on the first row and then the column. You can actually use information from the first run to limit the size of the size of the column, but the performance improvement will (in general) be relatively small.
The runtime for this is O(log m + log n)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment