Thread replies: 6
Thread images: 1
Thread images: 1
File: row-sorted matrix.png (7KB, 276x280px) Image search:
[Google]
7KB, 276x280px
What's the fastest way to search for an element in a row-sorted matrix?
e.g a matrix where going through the columns the numbers are random but when going through the rows the numbers are sorted in increasing order.
Would it be simply checking each row to see if the element fits in the range and then doing a binary search of each row that could possibly contain the element?
Pic related
>>
>>59448376
might just be quicker to binary search them from the start and skip the range check. if you were looking for the number 11 it fits in all those ranges so adding checks just add to the amount of work you have to do.
>>
>>59448376
Binary search / bisection method.
It's O(log(n))... the only change would be to walk through the array vertically which is shit easy.
>>
geeksforgeeks ddoott orgsearch-in-row-wise-and-column-wise-sorted-matrix
>>
>>59450542
that's for a fully sorted matrix, not just row-wise
>>
>>59448376
People are pretty good at picking out details in an otherwise meaningless field. Humans are optimized and evolved to be good at this kind of thing.
I suggest hiring someone and improving your local economy, plus gaining the pleasure of friendship in the process.
Hope this helps Anon.
Thread posts: 6
Thread images: 1
Thread images: 1