Find the Minimum Element in an Array — Read

Opening the reading…

The minimum must be a value from the array

For the array [7, 3, 9, 2, 6], the minimum is 2. The answer is not just a number that happens to be smaller than the others, it is an element that actually appears in the array. Your algorithm should therefore keep a candidate answer and compare it with every element.

CPPStarting the candidate at 0 fails for an array containing only positive values.

int min = 0;

for (int i = 0; i < 5; i++) {
    if (a[i] < min) {
        min = a[i];
    }
}

Starting min at 0 is unsafe. Every element in [7, 3, 9, 2, 6] is greater than 0, so the comparison a[i] < min is false at every index. The candidate stays 0 and the algorithm returns 0, even though 0 is not in the array.

The first element is a safe starting candidate

Use the first element as the initial candidate: min = a[0]. For this array, min starts as 7. The array must be nonempty, because a[0] must exist. Since index 0 is already represented by the candidate, the loop only needs to scan the remaining indices, from 1 through 4.

CPPThe first element initializes the candidate, so the loop begins at index 1.

int min = a[0];

for (int i = 1; i < 5; i++) {
    if (a[i] < min) {
        min = a[i];
    }
}

CHECKPOINT 1Not answered

Fill the initialization in min = ___ for [7, 3, 9, 2, 6].

int min = ___;

Checkpoints are not graded. They are here so you catch yourself before the quiz does — stuck, ask the tutor on the right.

The candidate changes only when a smaller value appears

The candidate starts at 7 because a[0] is 7. At index 1, the value is 3, and 3 < 7 is true, so the candidate becomes 3. At index 2, the value is 9, and 9 < 3 is false, so the candidate stays 3. At index 3, the value is 2, and 2 < 3 is true, so the candidate becomes 2. At index 4, the value is 6, and 6 < 2 is false, so the candidate stays 2.

INDEX PROCESSED	VALUE	COMPARISON	CANDIDATE AFTER COMPARISON
0	7	Starting value	7
1	3	3 < 7 is true	3
2	9	9 < 3 is false	3
3	2	2 < 3 is true	2
4	6	6 < 2 is false	2

Candidate values while scanning indices 0 through 4.

CHECKPOINT 2Not answered

Which candidate sequence is produced while scanning [7, 3, 9, 2, 6]?

Checkpoints are not graded. They are here so you catch yourself before the quiz does — stuck, ask the tutor on the right.

One complete scan proves that the final candidate is the minimum

After processing index i, the candidate is the smallest value among indices 0 through i. This remains true because a smaller value replaces the candidate, while a value that is not smaller leaves the candidate unchanged. After index 4, the candidate is therefore the smallest value among the whole array [7, 3, 9, 2, 6], which is 2.

The loop compares every element after the first exactly once, so the traversal takes O(n) time. The algorithm stores only the candidate and the index, so it uses O(1) extra space.