When working with arrays, there are a number of fundamental algorithms that you should memorize. You want these to become "second nature" so that you can pull them out of your toolbox when needed. These are:

• Counting for a match
• Cumulative algorithms
• Extreme values
• Linear and binary search
• Adjacent elements and the fencepost algorithm

You met most of these when working with vector, so this section will be mostly review.

Let's start with counting. To count all of the elements that match a condition:

counter <- 0
for each element in the array
    if the element matches the condition then
        counter <- counter + 1

Here's a traditional implementation of this that counts for exact matches to a value:

int aCount(const int a[], size_t len, int value)
{
    int counter = 0;
    for (size_t i = 0; i < len; ++i)
        if (a[i] == value) 
            counter++;
    return counter;
}

The iterator-based version of this algorithm, named count() is actually included in the standard library, in the header called <algorithm>. After including the header, you can call it like this:

#include <algorithm>
. . .
int a[] = {...};
. . .
cout << count(begin(a), end(a), value) << endl;

Cumulative algorithms such as sum, average, standard deviation, and so on, visit each element in the array and then add, multiply or otherwise process it.

Here is an example which adds all of the even numbers in an array named a:

• The array a is const, since the elements won't be changed.
• The accumulator sum is double so it doesn't overflow.
• Only the even elements (those where n % 2 == 0) are added.

double addEvens(const int a[], size_t len)
{
    double sum{0};
    for (size_t i = 0; i < len; ++i)
   { 
        if (a[i] % 2 == 0) { sum += a[i];} 
   } 
    return sum;
}

The largest (or smallest) value in a collection is called an extreme value. Here is the algorithm for finding the largest in an array:

largest <- first
For each remaining element 
   If element > largest Then
      largest <- element
Return largest

The algorithm for finding the smallest is similar. What if there is no first element? Then there is no largest or smallest element; it is an error condition.

For many algorithms, you not only want to know the largest (or smallest) value, but where it is located, either as an index or as a pointer. Click this link to look at both. We'll discuss the two functions in this example in the next section.

The biggest() function returns a pointer to the largest item in the array. We don't want to allow the element to change, and we don't want the pointer to be used to modify other elements, so the return type is const double* const.

When you call biggest(), you will dereference the returned pointer to get the value.

cout << *(biggest(da, 5)) << endl;

Let's apply the steps in the extreme values algorithm to this problem.

1. Save the first value as the largest. You need two variables to do this:

   const double *p = a;
   double largest = *p;

2. Now, loop through each remaining elementlike this:

   for (size_t i = 1; i < len; ++i)...

3. Each time through the loop, check to see if the current element is larger than the saved value, and, if so, update the saved values. Because you want to return a pointer, you'll need to update both largest and p. Note the use of the address operator.

   if (a[i] > largest){ 
       p = &a[i];
       largest = a[i];
   }

4. Finally, simply return the pointer p.

This is the same scheme used by the standard library algorithms min_element() and max_element(). When called using arrays, they return a pointer in exactly this manner.

Returning an index works almost the same as returning a pointer. Instead of the pointer, you need to keep track of the index. Here is the smaller() function which does that:

// Returns the index of the smallest value
// -1 if not found
int smallest(const double a[], size_t len)
{
    int result = -1; // not found
    if (len > 0)
   { 
        int smallest = a[0];
        result = 0;
        for (size_t i = 1; i < len; ++i)
       { 
            if (a[i] < smallest)
           { 
                result = i;
                smallest = a[i];
           } 
       } 
   } 
    return result;
}

To print an array, you want to surround all of the elements with delimiters (for instance brackets [] or braces {}), and separate the elements from each other by a comma. This is called the fencepost algorithm.

Here's the algorithm, assuming you have selected values for the opening and closing delimiters as well as the size.

Print opening delimiter (, {, [, etc.
If array size is > 0 Then
	Print first element
	For every remaining element
		Print separator
		Print element
Print closing delimiter

Click on this link to see this algorithm implemented as a template function .

What if you want to use the same algorithm, but print the elements in reverse order? That's a little more difficult. Here is an "obvious" algorithm which does not work correctly:

cout << a[len - 1];
for (size_t i = len - 2; i >= 0; --i)
{
    cout << separator << a[i];
}

The loop variable type is size_t, so as soon as you print a[0] and decrement the control variable i, instead of becoming -1, it "wraps around" and becomes the largest possible unsigned number. Since array subscripts are not range checked, the loop prints at larger and larger indexes until the program crashes.

This example below works correctly. Notice the extra if statement:

if (len > 0)
{
    cout << a[len - 1];
    for (size_t i = len - 1; i > 0; --i)
   { 
        cout << separator << a[i - 1];
   } 
}