CODEWITHSUNDEEP
c++arraysalgorithmmatrix
Đăng Khoa
Đăng Khoa

Reputation: 11

How to search for a vector in a matrix in C++ and which algorithm?

Suppose I have a matrix and a vector given by. How can I perform a search algorithm like binary search to return the index? Example:

const int V_SIZE = 10,H_SIZE = 7;
   int a1[V_SIZE][H_SIZE] = {
                                {1,2,0,0,0,0,0},
                                {1,3,0,0,0,0,0},
                                {2,2,4,0,0,0,0},
                                {2,2,6,0,0,0,0},
                                {3,2,4,7,0,0,0},
                                {4,1,3,5,9,0,0},
                                {4,1,4,6,8,0,0},
                                {4,2,3,4,7,0,0},
                                {5,2,3,5,7,8,0},
                                {6,1,3,4,5,7,10}
                            }; // sorted
  int a2 [H_SIZE] = {4,1,3,5,9,0,0};

Perform a search for the vector a2 in the matrix a1 and the return value is 6 Thank a lot

Upvotes: 1

Views: 869

Answers (3)

Dimitrios Bouzas
Dimitrios Bouzas

Reputation: 42909

You could use a 2D std::array in combination with std::lower_bound:

  const int V_SIZE = 10,H_SIZE = 7;
  std::array<std::array<int, H_SIZE>, V_SIZE> a1 {
                                {{{1,2,0,0,0,0,0}},
                                {{1,3,0,0,0,0,0}},
                                {{2,2,4,0,0,0,0}},
                                {{2,2,6,0,0,0,0}},
                                {{3,2,4,7,0,0,0}},
                                {{4,1,3,5,9,0,0}},
                                {{4,1,4,6,8,0,0}},
                                {{4,2,3,4,7,0,0}},
                                {{5,2,3,5,7,8,0}},
                                {{6,1,3,4,5,7,10}}
                            }}; // sorted

  std::array<int, H_SIZE> a2 {{4,1,3,5,9,0,0}};

  int idx = std::lower_bound(std::begin(a1), std::end(a1), a2) - std::begin(a1);

LIVE DEMO

Upvotes: 1

marom
marom

Reputation: 5230

What about something like this using std::array?

template <int HSIZE>
bool operator<(const std::array<int, HSIZE> &lhs, const std::array<int, HSIZE> &rhs)
{
    for (int i = 0; i < HSIZE; i++)
        if (lhs[i] != rhs[i])
            return lhs[i] < rhs[i];
    return false;
}

std::array<int, 7> a1[] = 
{
    { 1, 2, 0, 0, 0, 0, 0 },
    { 1, 3, 0, 0, 0, 0, 0 },
    { 2, 2, 4, 0, 0, 0, 0 },
    { 2, 2, 6, 0, 0, 0, 0 },
    { 3, 2, 4, 7, 0, 0, 0 },
    { 4, 1, 3, 5, 9, 0, 0 },
    { 4, 1, 4, 6, 8, 0, 0 },
    { 4, 2, 3, 4, 7, 0, 0 },
    { 5, 2, 3, 5, 7, 8, 0 },
    { 6, 1, 3, 4, 5, 7, 10 } 
};

void search(void)
{
    std::array<int, 7> a2 = { 4, 1, 3, 5, 9, 0, 0 };
    std::array<int, 7> *a1_end = a1 + sizeof(a1) / sizeof(std::array<int, 7>);
    std::array<int, 7> *it = std::lower_bound(a1, a1_end, a2);

}

Upvotes: 0

Some programmer dude
Some programmer dude

Reputation: 409206

If the matrix is sorted on the first number, you could use binary search to find an approximate index. You then have to go back until you find the first row starting with the same number as in the vector, as well as forward to find the last row starting with the same number. Then you loop over the vector, searching for a match for the second, third, etc. number in the range of rows you have.

Upvotes: 0

Related Questions