[C/C++] need a bit of help making a simple search engine.

[Piddler]

Hi, new to the forum, it is a really spiffy place. I'm not really much of a programmer, but I have an interest in it and kind of like to piddle around with programming. I am learning C and C++ mostly by doing, browsing books, and asking dumb questions of people who know a lot more about it than I do.

So here is a dumb question. I have been playing with arrays and I am trying to learn how to search through arrays. I managed to pull a piece of code from a book I've been reading ( I will show it below), and it works well. I want a search that will tell me if a number is in an array, and if so all of the locations that it can be found at.

Here is the code I found, it is a function and it is in C.

/* compare key to every element of array until the location is found
   or until the end of array is reached; return subscript of element
   if key or -1 if key is not found */
int linearSearch( const int A[], int key, int size )
{
   int n; /* counter */

   /* loop through array */
   for ( n = 0; n < size; ++n ) {

      if ( A[ n ] == key ) { 
         return n; /* return location of key */
      } /* end if */

   } /* end for */

   return -1; /* key not found */
} /* end function linearSearch */

the problem is that only returns the first one that it finds. how do I make it so that it returns all instances of the number matching the key?

Again, I am kind of a novice that just tinkers for fun, so go easy on me. Thanks, I really like your forums!

 

[rcgldr]

how do I make it so that it returns all instances of the number matching the key?

You need another array the same size as A[], perhaps name that second array B[]. Then you would fill up B[] with the indexes of A[] that matched the search value. You'd also need to return the actual number of matches, which would be the effective size of B[].

 

[I like Serena]

Hi Piddler! Welcome to PF.

Here's and adaptation:

/* compare key to every element of array; return the number of keys found.
   The found locations are stored in the array foundLocations.
   Note that foundLocations must be an array as big as A. */
int linearSearch( const int A[], int key, int size, int foundLocations[] )
{
   int n; /* counter */
   int nrFound = 0; /* number of keys found */

   /* loop through array */
   for ( n = 0; n < size; ++n ) {

      if ( A[ n ] == key ) { 
         foundLocations[ nrFound ] = n; /* store location of key */
         nrFound++;
      } /* end if */

   } /* end for */

   return nrFound; /* number of keys found */
} /* end function linearSearch */

 

[jtbell]

Here's a version that uses C++ vectors instead of arrays.

/* compare key to every element of vector A; return the number of keys found.
   The found locations are stored in the vector foundLocations. */
int linearSearch (const vector<int> &A, int key, vector<int> &foundLocations)
{
    /* get rid of anything that's already in foundLocations and set its size to 0 */
    foundLocations.clear();

    /* loop through vector A */
    for (int n = 0; n < A.size(); ++n)
    {
        if (A[n] == key)
        {
            foundLocations.push_back(n);
        }
    }

    return foundLocations.size();  /* number of keys found */
}

The size of A doesn't have to be passed as a separate parameter, because vectors "know" how big they are. Also, push_back() causes foundLocations to "grow" to exactly the size needed to accommodate the number of matches. In general, with vectors you don't have to do as much fussy "bookkeeping" with index variables, as you do with arrays.

Minor point: I put the declaration of n in the loop header instead of in a separate statement because n is used only inside the loop. I usually follow the principle that variables should be declared as "locally" as possible.

 

[LudusRex]

Hello there! It's great to see your interest in programming and I'm happy to help with your question. First of all, kudos to you for taking the initiative to learn by doing, browsing books, and asking questions - that's a great way to learn.

To address your question, the code you found is a linear search algorithm, which means it will only return the first occurrence of the key in the array. To return all instances of the number matching the key, you can modify the code to store the locations in an array and return that array instead. Here's an example of how you could do that:

/* compare key to every element of array until the location is found
or until the end of array is reached; return array of subscripts of elements
if key or empty array if key is not found */
int[] linearSearch( const int A[], int key, int size )
{
int n; /* counter */
int count = 0; /* counter for number of occurrences */
int locations[size]; /* array to store locations */

/* loop through array */
for ( n = 0; n < size; ++n ) {

if ( A[ n ] == key ) {
locations[count] = n; /* store location in array */
count++; /* increment counter for next location */
} /* end if */

} /* end for */

/* check if key was found at least once */
if (count > 0) {
return locations; /* return array of locations */
} else {
int emptyArray[0]; /* create empty array if key was not found */
return emptyArray;
}
} /* end function linearSearch */

I hope this helps you with your search engine project. Keep tinkering and learning, and don't hesitate to ask more questions if you need help. Good luck!