[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.