Algorithms & Flowcharts — Worked Examples

11. Working with Lists & Arrays

Scanning a list

A huge number of real programs boil down to one idea: walk through a list once, remembering something as you go. The "something you remember" might be the biggest value seen so far, the smallest, a running count, or the best two values. The pattern is always the same — start with a sensible first guess, then update it whenever you find something better. Every example below uses the sample list [4, 9, 2, 9, 7].

(a) Find the maximum (and its position)

Problem

Given a list of numbers, find the largest value and the index where it first appears.

Pseudocode

FIND_MAX(a):
    best = a[0]
    pos  = 0
    FOR i FROM 1 TO length(a) - 1:
        IF a[i] > best:
            best = a[i]
            pos  = i
    OUTPUT best, pos

Trace table

i	a[i]	a[i] > best?	best	pos
init	—	—	4	0
1	9	Yes	9	1
2	2	No	9	1
3	9	No (not strictly greater)	9	1
4	7	No	9	1

In Python

def find_max(a):
    best, pos = a[0], 0
    for i in range(1, len(a)):
        if a[i] > best:
            best, pos = a[i], i
    return best, pos

print(find_max([4, 9, 2, 9, 7]))

Output:

(9, 1)

(b) Find the minimum

Problem

Find the smallest value in a list of numbers.

Pseudocode

FIND_MIN(a):
    low = a[0]
    FOR i FROM 1 TO length(a) - 1:
        IF a[i] < low:
            low = a[i]
    OUTPUT low

Trace table

i	a[i]	a[i] < low?	low
init	—	—	4
1	9	No	4
2	2	Yes	2
3	9	No	2
4	7	No	2

In Python

def find_min(a):
    low = a[0]
    for i in range(1, len(a)):
        if a[i] < low:
            low = a[i]
    return low

print(find_min([4, 9, 2, 9, 7]))

Output:

(c) Count how many times a value occurs

Problem

Count how many times a target value (here, 9) appears in the list.

Pseudocode

COUNT(a, target):
    count = 0
    FOR i FROM 0 TO length(a) - 1:
        IF a[i] == target:
            count = count + 1
    OUTPUT count

Trace table

Counting occurrences of 9 in [4, 9, 2, 9, 7]:

i	a[i]	a[i] == 9?	count
init	—	—	0
0	4	No	0
1	9	Yes	1
2	2	No	1
3	9	Yes	2
4	7	No	2

In Python

def count_value(a, target):
    count = 0
    for x in a:
        if x == target:
            count += 1
    return count

print(count_value([4, 9, 2, 9, 7], 9))

Output:

(d) Find the second-largest value

Problem

Find the second-largest value in a list by tracking the two best values seen so far.

Pseudocode

SECOND_LARGEST(a):
    best   = -infinity
    second = -infinity
    FOR each x IN a:
        IF x > best:
            second = best
            best   = x
        ELSE IF x > second AND x < best:
            second = x
    OUTPUT second

Trace table

Scanning [4, 9, 2, 9, 7]. (Note the duplicate 9 is not greater than best, so it is skipped — the second-largest distinct value is 7.)

x	x > best?	best	second
init	—	-inf	-inf
4	Yes	4	-inf
9	Yes	9	4
2	No (2<4)	9	4
9	No (not > best, not < best)	9	4
7	No, but 4<7<9	9	7

In Python

def second_largest(a):
    best = second = float("-inf")
    for x in a:
        if x > best:
            second, best = best, x
        elif second < x < best:
            second = x
    return second

print(second_largest([4, 9, 2, 9, 7]))

Output: