Implementing Array Algorithms
Introduced| English |
|---|
| traversal/træˈvɜːsl/ |
| index/ˈɪndeks/ |
| linear search/ˈlɪnɪə sɜːtʃ/ |
Standard array algorithms
- Most array tasks are a traversal 遍历 plus one of a few standard patterns.
- Sum / average: accumulate a total, then divide by
length. - Count: increment when an element matches a condition.
- Min / max: track the smallest or largest seen so far.
Finding the maximum
- Start
max = a[0](the first element), then traverse from index1. if (a[i] > max) { max = a[i]; }inside the loop.- After the loop,
maxholds the largest value in the array. - Start from the first element, not
0—0could be larger than every value.
Searching for a value
- To check if a value is present, traverse and compare each element.
- Return the index 下标 where it's found, or
-1if the loop finishes without a match. if (a[i] == target) return i;inside the loop;return -1;after.- This is a linear search 线性查找 (Unit 4.14 covers it in depth).
Shifting and modifying
- Some algorithms move or change elements — e.g. shift everything left, or double each value.
- Modifying needs the indexed loop so you can assign
a[i] = .... - Watch bounds when reading
a[i+1]— the last index has no neighbor. - Trace the indices carefully to avoid an out-of-bounds access.
Initialize a max/min search with the FIRST element, not 0. int max = 0; fails if every value is negative (it would wrongly report 0). Use int max = a[0]; and start the loop at index 1. And when an algorithm reads a[i+1], stop the loop at i < a.length - 1, or the last iteration reads past the end.
Finding the maximum of a:
int max = a[0];for (int i = 1; i < a.length; i++) { if (a[i] > max) max = a[i]; }- For
a = {3, 9, 5}: max becomes9.
Array algorithms combine a traversal with a pattern: sum/average, count, min/max, or search (return the index or -1). Initialize a min/max with the first element, not 0. Modifying elements needs the indexed loop, and reading a[i+1] needs a tighter bound to stay in range.
Finding the maximum
max starts at a[0]=3, becomes 9, then stays (a = {3,9,5}).
To find the maximum of an array, you should initialize max to...
Starting at 0 fails if all values are negative.
For a = {3, 9, 5}, what is the maximum value?
9 is the largest element.
A linear search returns what if the target is not found?
By convention, -1 means 'not found'.
An algorithm that reads a[i+1] should loop while...
Stopping one early keeps a[i+1] in bounds.
Modifying array elements (a[i] = ...) requires the indexed loop, not for-each.
for-each can't assign back into the array.