找到你要的答案

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

Q:如何寻找在C++矩阵向量的算法?

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

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

answer1: 回答1:

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

你可以使用一个2D 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);

现场演示

answer2: 回答2:

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.

如果矩阵在第一个数上进行排序,则可以使用二进制搜索来找到近似索引。然后,您必须返回,直到您发现第一行开始与向量相同的号码,以及向前找到最后一行相同的号码。然后在vector上循环,在所选行的范围内搜索第二个、第三个等号码的匹配。

answer3: 回答3:

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);

}

像这样的使用STD:数组?

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);

}
c++  arrays  algorithm  matrix