Vinc_get31 wrote:

A= [1 1 7]

[1 2 5]

[2 4 7]

[3 5 8]

B= [1 1 2]

[1 2 3]

[1 3 4]

[1 4 3]

[1 5 0]

[2 1 7]

[2 2 2]

[2 3 7]

[2 4 1]

[2 5 7]

[3 1 1]

[3 2 4]

[3 3 7]

[3 4 0]

[3 5 0]

And I want, with the function I'm looking for, this result :

C=f(B)= [1 1 2]

[1 2 3]

[2 4 1]

[3 5 0]

Well. First of all. Make sure things are sorted! Searching is

always easier and faster if things are sorted. That's why

phone books are sorted :-)

Sort your B matrix according to the first and second column.

Your posted example already has the correct sort order. I don't

know if this was intended or if it is just a concidence, that's

why I address this issue.

There are multiple strategies you could use.

A general one is this:

Take a row from the A matrix -> 2 4 7

You are looking for a row in the B vector which starts with a 2.

So do a binary search to locate a row that starts with 2

Eg. The binary search in the first column will bring you to:

[1 1 2]

[1 2 3]

[1 3 4]

[1 4 3]

[1 5 0]

[2 1 7]

[2 2 2]

[2 3 7] <-

[2 4 1]

[2 5 7]

[3 1 1]

[3 2 4]

[3 3 7]

[3 4 0]

[3 5 0]

that is a row [ 2 3 7 ] which starts with 2. Since you are looking for [ 2 4 7 ]

and 4 is greater then 3, do a search backwards until you either find a row

which starts with [ 2 4 . ] or the first column is no longer a 2 or the

second row element is greater then 4 (remember: the entries are sorted !)

In the second case and third case, there is no row which starts with [2 4 .]

If on the other hand the binary search dropped you at an entry [ 2 5 7 ]

and you are still searching for [ 2 4 7 ], then you know that the row, if

it is in the matrix is before [ 2 5 7 ]. So continue search frontwards until

you either find a row that fits or the second column has a value smaller then 4,

or the first column has a value smaller then 2. In this cases there is no

row that fits your needs.

Basically that's it. Repeat the whole process for the next search row and

collect the results.

If you think this is complicated: not at all. You have done the very same thing

hundreds of times: Whenever you search a phone number in a phone book, you do

the very same thing: First locate the page which contains the last name, eg

by opening the book in the middle and deciding if the searched name is before

of after that page. Repeat that process until you find a page which contains the

last name (that's the binary search step). If there are multiple first names with

the same last name, just pick one and decide if the searched first name is in front

of or after the one you search for.

You see: coming up with algorithms is often a question of watching carfully what

you do in real life :-)

Various variations are possible. Eg. if the numbers in your matrix are limited

to lets say the a range of 0 to 9, then an additional array containing the

starting indices of those numbers in the first row may replace the binary

search step. (That would be equivalent with having an index in the phone book:

you are looking for a last name that starts with C. Don't worry searching the

whole book, all names starting with C are on page 78ff)

--

Karl Heinz Buchegger

kb******@gascad.at