How do I linear search two arrays in c++?

Question

I have two arrays of data type double - called array1[10] and array2[8]. I am required to search for array2 inside array1 at each element using a linear search function. The function declaration is

string linSearch (double array1[10], double array2[8]);

If array2 is found inside array1 then I need to print out the index of where it is found in array1. If its not found I need the output to be "NA". This output must be a delimited-comma- string. eg.

//given the two arrays:
array1={1.1,1.2,6,7,3.5,2,7,8.8,9,23.4}
array2={6,45,2,7,1.1,5,4,8.8}

//after the linear search completes, the output must be the index in which //array2 is found in array1. if its not found, then it must be NA:

2,NA,5,6,0,NA,NA,7

So far I have the code that follows. Its my first time working with arrays and I am still having difficulties grasping the concept- like once I define the function how do I even call it in the main program?! anyway..the function definition I have (excluding the main program) is:

string linSearch (double array1[10], double array2[8])
{
    int index1 = 0;
    int index2 =0;
    int position =-1;
    bool found = false;
    while (index1<10 && !found && index2<8)
    {
        if array1[index1] == array2[index2])
        {
            found = true;
            position = index1;
        }
        index1++;
        index2++;
    }

    return position;

}

I am EXTREMELY confused about searching for one array in the other and how to output the delimited list as well as how to connect it to my main program. Any help would be GREATLY appreciated. Thanks!

Answer 1

In your example of arrays and the expected output

//given the two arrays:
array1={1.1,1.2,6,7,3.5,2,7,8.8,9,23.4}
array2={6,45,2,7,1.1,5,4,8.8}

and

2,NA,5,6,0,NA,NA,7
       ^

there is a typo. The output should be

2,NA,5,3,0,NA,NA,7
       ^

because the number 7 is found in the third position of the array array1.

Here you are.

#include <iostream>
#include <string>
#include <sstream>

std::string linearSearch( const double a1[], size_t n1, const double a2[], size_t n2 )
{
    std::ostringstream os;

    for ( size_t i = 0; i < n2; i++ )
    {
        if ( i != 0  ) os << ',';

        size_t j = 0;

        while ( j < n1 && a2[i] != a1[j] ) ++j;

        if ( j == n1 ) os << "NA";
        else os << j;
    }

    return os.str();
}


int main() 
{
    double a1[] = { 1.1, 1.2, 6, 7, 3.5, 2, 7, 8.8, 9, 23.4 };
    const size_t N1 = sizeof( a1 ) / sizeof( *a1 );
    double a2[] = { 6, 45, 2, 7, 1.1, 5, 4, 8.8 };
    const size_t N2 = sizeof( a2 ) / sizeof( *a2 );

    std::cout << linearSearch( a1, N1, a2, N2 ) << '\n';

    return 0;
}

The program output is

2,NA,5,3,0,NA,NA,7

Answer 2

You are not searching one array inside the other. You are searching for elements from one array in a second array. If you are using a linear search and if you do not want to sort the array, you need 2 nested loops to do that. One for each element in the second array, and one to find that element in the first array.

Keep things simple and start with finding the position of a single element in one array. Because you are comparing doubles, you should not compare them with ==. Next you just need a function that calls the first for each element in the second array:

#include <string>
#include <vector>
#include <algorithm>    
#include <iostream>


void index_to_string(const std::vector<double>& v,double e,std::ostream& out){
    auto it = std::find_if(v.begin(),
                           v.end(),
                           [e](const double& x) {
                               return std::abs(e-x) < 1e-8;
                           }
                        );
    if (it == v.end()) {
        out << "NA";
    } else {
        out << (it - v.begin());
    }
}

void all_indices_to_string(const std::vector<double>& v1,const std::vector<double>& v2,std::ostream& out){
    if (v1.size() == 0 || v2.size()==0) return;
    index_to_string(v1,v2[0],out);
    for (size_t i=1;i<v2.size();++i){
        out << ",";
        index_to_string(v1,v2[i],out);
    }
}

int main() {
    double array1[] ={1.1,1.2,6,7,3.5,2,7,8.8,9,23.4};    
    double array2[] ={6,45,2,7,1.1,5,4,8.8};
    all_indices_to_string(
        std::vector<double>(std::begin(array1),std::end(array1)),
        std::vector<double>(std::begin(array2),std::end(array2)),
        std::cout
    );
}

Output:

2,NA,5,3,0,NA,NA,7

Answer 3

#include <iostream>
using namespace std;

string linSearch(double array1[10], double array2[8])
{

    string result = "";
    bool found;
    for (int j = 0; j < 8; j++)
    {
        if(j > 0)
            result.append(", ");

        found = false;
        for (int i = 0; i < 10; i++){
            if (array1[i] == array2[j]) {
                result.append(to_string(i));
                found = true;
            }
        }
        if(!found)
            result.append("NA");
    }
    return result;
}

int main(){

    double a1[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    double a2[8] = {11, 25, 3, 41, 5, 6, 7, 8};
    cout << linSearch(a1, a2) << endl;
    return 0;
}