BrewlearnCommon array algorithms in Java
Sum, max, reverse, linear search, counting.
Sum and count
Two patterns you'll write a thousand times. Sum (accumulate): start at 0, add each element. Count: start at 0, and count++ whenever a test passes.
int sum = 0, count = 0;
for (int x : a) {
sum += x; // accumulate
if (x > 4) count++; // count matches
}Your turn
How many odd numbers?
int[] a = {4, 9, 2, 9, 7};
int n = 0;
for (int x : a) {
if (x % 2 == 1) n++;
}
System.out.println(n);2345
Show the answer
9, 9 and 7 are odd (x % 2 == 1), so the count is 3. The 4 and 2 don't pass the test.
Max: best so far
To find the maximum, track the best value seen so far and replace it whenever you meet something bigger. **Start with a[0]**, a real element, not 0.
int max = a[0];
for (int x : a) {
if (x > max) max = x;
}The negative test
Every temperature is below zero. What prints?
int[] t = {-8, -3, -12};
int best = 0;
for (int x : t) {
if (x > best) best = x;
}
System.out.println(best);-30-12
Show the answer
0! No element is greater than 0, so best is never updated, and the result is a value that isn't even in the array. Starting with best = t[0] gives the right answer, -3.
Linear search
Check each element in turn. Return the index as soon as you find it; if the loop finishes, return -1. Why -1? It can never be a valid index, so callers can tell "not found" apart from a real position (0 *is* valid). And i is out of scope after the loop anyway.
static int indexOf(int[] a, int target) {
for (int i = 0; i < a.length; i++) {
if (a[i] == target) return i;
}
return -1; // not found
}Reverse: stop at the middle
To reverse in place, swap a[i] with a[n - 1 - i], moving inward. But **only while i < n / 2! If the loop runs the full length, the second half swaps every pair back again** and the array ends up unchanged.
for (int i = 0; i < a.length; i++) { // bug
int t = a[i];
a[i] = a[a.length - 1 - i];
a[a.length - 1 - i] = t;
} // swaps everything twice!Reverse, done right
What prints?
int[] a = {1, 2, 3, 4, 5};
int n = a.length;
for (int i = 0; i < n / 2; i++) {
int t = a[i];
a[i] = a[n - 1 - i];
a[n - 1 - i] = t;
}
System.out.println(Arrays.toString(a));[5, 4, 3, 2, 1][1, 2, 3, 4, 5][5, 2, 3, 4, 1]
Show the answer
With 5 elements, a.length / 2 is 2, so only i = 0 and 1 swap: (1, 5) and (2, 4). The middle element 3 stays put. Result: fully reversed.
In real projects
These five shapes (sum, count, max, search, reverse) appear in coding interviews constantly, and in disguise all over real code: totals in a shopping cart, the highest bid in an auction, finding a user by ID. Java's streams can do many of them in one line, but you'll only trust those once you know the loop underneath.
Key takeaways
- Max: start with a[0], not 0, because all values might be negative
- Linear search: return the index when found, -1 after the loop
- Reverse in place: swap a[i] and a[n - 1 - i] only while i < n / 2
- Count: if (test) count++;
In 2006 Joshua Bloch revealed that Java's own Arrays.binarySearch had a bug for about nine years: computing the middle as (low + high) / 2 could overflow on huge arrays.
Practice questions
What does this print?
int[] a = {3, 8, 1, 8, 5};
int count = 0;
for (int x : a) {
if (x > 4) count++;
}
System.out.println(count);- 2
- 3
- 1
- 4
Check your answer
3. The elements greater than 4 are 8, 8 and 5, so count is 3.
Which value should linear search return when the target isn't found?
static int indexOf(int[] a, int target) {
for (int i = 0; i < a.length; i++) {
if (a[i] == target) return i;
}
return ___;
}- i
- 0
- -1
- target
Check your answer
-1. -1 can never be a valid index, so callers can tell 'not found' apart from a real position. 0 is a valid index, and i is out of scope after the loop.