2015-02-10

We can distinguish several different kinds of searches in array:

- Find the index of the first occurrence of a particular value. Return a negative number to flag failure.
- Find the index of the
occurrence of a particular value. Return a negative number to flag failure.**last** - Find the largest value in the array. One could also find the index of that value.
- Find the smallest value in the array. Again, it could be the index of that value.

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