Ordered Matrix search

[indiocolifa]

I need to search a value in a matrix ordered in increasing form such as A[i,j] <= A[i+1,j] and A[i,j] <= A[i,j+1].

I don't want to do a linear search which is O(n^2), there is any form to search subdividing the matrix like in a binary search ?

Thanks.

[DragForce]

First do binary search for diagonal elements. If the required element is not there, then you will know row and column which may contain it. Do binary search for both of them. The complexity wil be O(log n) as required.

[indiocolifa]

Thank you for your response, I was doing the search by a selfmade algorithm which is not O(log n), but it's enough for my purposes.

Suppose that in a ordered matrix as described in my first message such as:

| a b c d |
| e f g h |
| i j k l |
| mn o p |

The steps:

I get the value at M[n/2, n] ( above is H )

* If x = M[n/2] return.
* If x < M[n/2] the value is in the upper-half.
* If x > M[n/2] the value is on the bottom half.

I do a binary search per row on the upper or bottom half for the value.

I think that this algorithm is of complexity O(n/2 * log(N))...

I'm right?

Thank you very much.

PD: Your algorithm seems not hard to implement

[remyang]

What if j<h and you're supposed to search for j?

[indiocolifa]

What if j<h and you're supposed to search for j?

The algorithm uses binary search so the matrix it's supposed to be ordered such as the following rules apply:

* M[i,j] < M[i+1, j]
* M[i,j] < M[i,j+1]

[remyang]

the rules means that each row and column is sorted, but it doesn't necessarily guarantee the order between two items that are on differen rows and columns.

For example, the following matrix

1 2 3
4 5 6
7 8 9

if you switch 6 and 7,

1 2 3
4 5 7
6 8 9

it still abides by the rules, but your algorithm will fail if it's asked to search fo 6.