CODEWITHSUNDEEP
c++arrays
JorensM
JorensM

Reputation: 480

C++ two array element search

i've come across a problem.

How do i check if an array has two,or more elements in a sequence.

For example,let's say i have an array

1,2,3,6,7,8,4,5

and i want to check if it has numbers 6,7,8 but in that sequence.

For example,if it would be

1,2,3,7,6,8,4,5

it would return false.

I know that it's pretty easy with one element,just make a for loop,but i can't figure out how to search for two or more arrays,and in the sequence i want them to be.

Upvotes: 0

Views: 609

Answers (2)

formiaczek
formiaczek

Reputation: 425

This is should yield O(n):
(edit: but it works correctly only with sequences that don't contain cycles)

bool has_a_sequence(const std::vector<int>& where, const std::vector<int>& seq_no_cycles)
{
    if(!seq_no_cycles.size())
    {
        return false;
    }
    std::vector<int>::const_iterator where_iter;
    std::vector<int>::const_iterator seq_iter = seq_no_cycles.begin();    
    for(where_iter = where.begin(); where_iter != where.end(); where_iter++)
    {
        if(*where_iter == *seq_iter)
        {
            seq_iter++;
            if(seq_iter == seq_no_cycles.end())
            {
                break;
            }
        }
        else
        {
            seq_iter = seq_no_cycles.begin();
            if(*where_iter == *seq_iter)
            {
                seq_iter++;
            }
        }
    }
    return seq_iter == seq_no_cycles.end();
}

Upvotes: 0

ipc
ipc

Reputation: 8143

There's an algorithm for that: std::search. Use it and don't care (only care if you want have something sophisticated that is faster than O(n·m)).

// will be superfluous in C++11
template <typename T, std::size_t N> T *begin(T (&arr)[N]) { return arr; }
template <typename T, std::size_t N> T *end  (T (&arr)[N]) { return &arr[N]; }

int main()
{
  int array[] = {1,2,3,6,7,8,4,5};
  int check[] = {6,7,8};

  int *position = std::search(begin(array), end(array), begin(check), end(check));
  if (position != end(array))
    std::cout << "found at position " << position - array << '\n';
  else
    std::cout << "not found\n";
}

Upvotes: 5

Related Questions