CSCD-255
2015-02-10


Searching Arrays (Ch. 22)

We can distinguish several different kinds of searches in array:

Finding the index of a particular value is an example of where we can exit the loop on success, and indeed can do that by returning the index.
First occurrence:  FindFirst.txt   FindFirst.c   FindFirst.exe

Finding the index of the last occurence can be approached two ways:
Scanning forward:  FindLast.txt   FindLast.c   FindLast.exe
Scanning Backwards allows early exit:  FindReverse.txt   FindReverse.c   FindReverse.exe

If we have the array and the index of the largest (or smallest) value, we necessarily have access to that value, so that is the kind of search we will do.

The basic strategy is this:  assume that first entry is indeed the largest entry, and then go through the rest of the loop, correcting as required.

/*
 * Find the subscript of the largest entry.
 */
int maxIdx ( int x[], int n )
{  int big = 0,    // Subscript of largest encountered
       k;          // Loop variable

   for ( k = 1; k < n; k++ ) // Start at 1 --- no need to check 0
      if ( x[big] < x[k]) )  // I.e., NOT the biggest so far
         big = k;            // correct the value in big.
   return big;
} // end maxIdx()

Finding the largest:  FindMax.txt   FindMax.c   FindMax.exe
Finding the smallest:  FindMin.txt   FindMin.c   FindMin.exe

Note that in the main program, there is a single statement calling maxIdx (largest_index = maxIdx(x, limit);) but that statement requires as much time as the function itself takes.  In other words, the loop will have to be traversed n-1 times (since the for loop's index starts at 1, not 0 —for ( k = 1; k < n; k++ )).  So in analyzing how much time it will take we call it a linear time algorithm:  it scales with n.

Parallel arrays
One can have arrays of different types storing information about the same things.  In this example, there is an array of character strings holding the titles of the seven Harry Potter books, an array of integers holding the number of pages, and an array of floats holding the price quoted on Amazon.com.  Thus, for each k, title[k] has pages[k] pages and costs price[k].
parallel.txt   parallel.c   parallel.exe