Welcome to Implementing Array Algorithms!

In previous chapters, like Array Creation and Access and Array Traversals, you learned how to build an array and "walk" through it using loops. In this chapter, we are going to learn what to actually do while we are walking! Think of an algorithm as a "recipe." We are learning the standard recipes that computer scientists use to solve everyday problems with data sets.

Don't worry if logic feels a bit like a puzzle at first. Most of these algorithms follow a very predictable pattern: Initialize a variable, Loop through the array, and Update the variable based on what you find.

1. Finding the Sum and Average

The most common task is adding up all the numbers in an array. To do this, we use the Accumulator Pattern. We create a "bucket" (a variable) to hold our total and add each element to it one by one.

The Logic:
1. Create a variable called \( sum \) and set it to \( 0 \).
2. Loop through every index \( i \) from \( 0 \) to \( array.length - 1 \).
3. Inside the loop, add the current element to \( sum \).
4. To find the average, divide the \( sum \) by \( array.length \).

Quick Tip: When calculating the average, remember that if your array contains integers, you should cast the sum to a \( double \) before dividing to avoid integer division (which would chop off the decimal!). For example: \( average = (double) sum / array.length \).

2. Finding a Minimum or Maximum

Imagine you are looking for the tallest student in a line. You look at the first person and say, "You're the tallest so far." Then you look at the second person. If they are taller, they become the new "tallest so far." This is exactly how we find the maximum value in an array.

The Logic for Maximum:
1. Initialize a variable \( max \) to the very first element: \( array[0] \).
2. Loop through the rest of the array (starting at index \( 1 \)).
3. If the current element \( array[i] \) is greater than \( max \), update \( max \) to be that element.
4. After the loop finishes, \( max \) holds the largest value.

Common Mistake: Do not initialize \( max \) to \( 0 \) if your array could contain negative numbers! If your array is \( \{-5, -10, -3\} \), a \( max \) initialized to \( 0 \) would stay \( 0 \), which isn't even in the array! Always initialize to \( array[0] \) or the smallest possible integer: \( Integer.MIN\_VALUE \).

Sometimes you just need to know how many times a specific value appears, or where that value is located.

Counting

This is just like the sum algorithm, but instead of adding the element's value, you add \( 1 \) to a counter only if the element matches a specific condition.

Linear Search

Linear Search is the simplest way to find something: you start at the beginning and look at every single item until you find a match.

1. Loop through the array.
2. If \( array[i] \) equals the target value, return the index \( i \).
3. If the loop ends and you never found it, return \( -1 \) to signify the value isn't there.

Did you know? We call this "Linear" search because the time it takes grows in a straight line as the array gets bigger. If the array is twice as long, it potentially takes twice as long to search.

4. Reversing and Shifting Elements

These algorithms "move" the data around within the array. These are often the trickiest for students because you have to be careful not to overwrite data before you've moved it!

Reversing an Array

To reverse an array, you swap the first and last elements, then the second and second-to-last, and so on. You stop when you reach the middle \( (array.length / 2) \). If you go all the way to the end, you'll just swap everything back to its original spot!

Shifting Elements

Shifting means moving every element one spot to the left or right.

  • Left Shift: The element at index \( 1 \) moves to index \( 0 \), index \( 2 \) moves to \( 1 \), etc. Usually, the first element is saved in a temporary variable so it can be moved to the very end (this is called a circular shift).
  • Right Shift: You must loop backwards! If you start at the front, you will overwrite the second element before you've had a chance to move it.

5. Identifying the Right Loop

When implementing these algorithms, you have two main choices: the Standard for-loop and the Enhanced for-loop (for-each). Here is a quick cheat sheet for when to use which:

Use an Enhanced for-loop if:
- You are looking at every element.
- You don't need to know the index (\( i \)).
- You are not modifying the array (changing which objects are in which slots).
Example: Summing, Finding Max, Counting.

Use a Standard for-loop if:
- You need the index (\( i \)) for a calculation.
- You are only looking at part of the array (e.g., starting at index \( 1 \)).
- You are changing the array (shifting or reversing).
Example: Shifting, Reversing, Linear Search (where you return the index).

Quick Review: Key Takeaways

1. Accumulators: Start at \( 0 \) and add as you go.
2. Comparison: Start at \( array[0] \) and update if a "better" match is found.
3. Boundaries: Always check your loop limits to avoid the dreaded \( ArrayIndexOutOfBoundsException \). Remember, the last valid index is always \( array.length - 1 \).
4. Swapping: Always use a "temporary" variable when moving or swapping elements so you don't lose data.

Note: For more on how to set up the basic loops used here, refer back to the Array Traversals chapter.