Vinc_get31 said:
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)
