Check whether two elements have a common element in C++

Question

I want the function to return true when there is any element matching between two vectors,

Note : My vectors are not sorted Following is my source code,

bool CheckCommon( std::vector< long > &inVectorA, std::vector< long > &inVectorB )
{
    std::vector< long > *lower, *higher;

    size_t sizeL = 0, sizeH = 0;

    if( inVectorA.size() > inVectorB.size() )
    {
        lower = &inVectorA;
        sizeL = inVectorA.size();
        higher = &inVectorB;
        sizeH = inVectorB.size();
    }
    else
    {
        lower = &inVectorB;
        sizeL = inVectorB.size();
        higher = &inVectorA;
        sizeH = inVectorA.size();
    }

    size_t indexL = 0, indexH = 0;

    for( ; indexH < sizeH; indexH++ )
    {
        bool exists = std::binary_search( lower->begin(), lower->end(), higher->at(indexH) );

        if( exists == true )
            return true;
        else
            continue;
    }
    return false;
}

This is working fine when the size of vector B is less than the size of vector A , but returning false even there is match when size of vector B is greater than size of vector A .

Answer 1

The problem with posted code is that you should not use std::binary_search when the vector is not sorted. The behaviour is defined only for sorted range.

If the input vectors are not sorted then you can use find_first_of to check for existence of first common element found.

bool CheckCommon(std::vector<long> const& inVectorA, std::vector<long> const& nVectorB)
{
    return std::find_first_of (inVectorA.begin(), inVectorA.end(),
                               nVectorB.begin(), nVectorB.end()) != inVectorA.end();
}

Complexity of find_first_of is up to linear in inVectorA.size()*inVectorB.size(); it compares elements until a match is found.

If you want to fix your original algorithm then you can make a copy of one of vectors and std::sort it, then std::binary_search works with it.

In actual programs that do lot of such matching between containers the containers are usually kept sorted. On such case std::set_intersection can be used. Then the complexity of search is up to linear in inVectorA.size()+inVectorB.size().

std::find_first_of is more efficient than to sort both ranges and then to search for matches with std::set_intersection when both ranges are rather short or second range is shorter than binary logarithm of length of first range.

Answer 2

You can use a well-defined algorithm called as std::set_intersection to check if there is any common element between these vectors.

Pre-condition :- Both vectors be sorted.