Searching a sorted matrix (young tableau) in O(n) time?

[Saeven]

Hello,

I was curious if anyone had some good algorithms to search through a row and column sorted square matrix in O(n)-time.

Cheers.
Alex

[panayotisk]

If it is sorted why not use binary search?
This is O(logN) if I remember well...
If both Dimensions are sorted then it should be 2*O(logN). Correct me if I am wrong

[SolarFlare]

Binary search is the best way to do it if it's already sorted... unless you didn't actually mean the matrix was sorted, but somehow otherwise "arranged" and that such a search would not work.

[Saeven]

Hi guys,

When you say binary search, I'm assuming that you are planning on the mod trick to index the row/col into an array. Don't forget however, that this will not work on a young tableau.

For instance:

1 - 2 - 3 - 4 - 5
2 - 3 - 4 - 5 - 6
4 - 5 - 7 - 8 - 9
......

Will fail the binary search entirely. Don't forget this is an nxn matrix, and O(n) time means linear. Binary search on each would take nlgn which is too long.

My belief is that percolation is still the best method at this point. I just wanted to know if there were some interesting tricks on this topic out there.

Thanks.
Alex

[SolarFlare]

Originally posted by Saeven
Hi guys,

When you say binary search, I'm assuming that you are planning on the mod trick to index the row/col into an array. Don't forget however, that this will not work on a young tableau.

For instance:

1 - 2 - 3 - 4 - 5
2 - 3 - 4 - 5 - 6
4 - 5 - 7 - 8 - 9
......

Will fail the binary search entirely. Don't forget this is an nxn matrix, and O(n) time means linear. Binary search on each would take nlgn which is too long.

My belief is that percolation is still the best method at this point. I just wanted to know if there were some interesting tricks on this topic out there.

Thanks.
Alex
Well that's what was unclear... when you say it is "sorted", what are the conditions of this sort?

M[i][j+1]>M[i][j]
M[i+1][j]>M[i][j]

are implied from your example matrix (which by the way is not nxn), any others?

[Saeven]

Hello,

The definition of a young tableau is that it is nxn, and that it is row and column sorted.


are implied from your example matrix (which by the way is not nxn), any others?


Notice the suspension points below the last row. This is solely a question related to young tableau.

Regards.
A

[Yves M]

A box-type binary search would do the trick. The idea is to segment the matrix into squares of decreasing size. You start off by comparing your search value (call it A) to the value in the matrix at (n / 2, n / 2). If equal, you found it, if it's smaller, then the value cannot be in the submatrix (n/ 2 -> n, n/2 -> n). If it's bigger then it can't be in the submatrix (1 -> n/2, 1->n/2). This reduces the size of the problem by a factor of 0.75.

After this step, you have 3 'boxes' in which it can appear. You can eliminate two of them (not always) by comparing the value to the smallest value in the corresponding box (the upper left value). Then you recursively try to find the value in each of the remaining boxes.

I've just tried it and it's *much* faster than the row by row binary search (of course). Complexity is O(log N) in the average and worst case.

[Yves M]

Here is the source code.

[hiram.abbas]

How can you prove it's O(log n)?

If only one quarter is left after each step, it is O(log n). As you said it's not always possible. Two quarters, O(n). Three quarters, O(n^1.58).