Searching for the Two Smallest Values

This section will explore how to find the index of the two smallest items in an unsorted list using three quite different algorithms. We’ll go through a top-down design using each approach.

To start, suppose we have data showing the number of humpback whales sighted off the coast of British Columbia over the past ten years:

The first value, 809, represents the number of sightings ten years ago; the last one, 476, represents the number of sightings last year.

We’ll start with a simpler problem: what is the smallest value during those years? This code tells us just that:

If we want to know in which year the population bottomed out, we can use list.index to find the index of the smallest value:

Or, more succinctly:

Now, what if we want to find the indices of the two smallest values? Lists don’t have a method to do this directly, so we’ll have to design an algorithm ourselves and then translate it to a Python function. Here is the header for a function that does this:

As you may recall from ​Designing New Functions: A Recipe​, the next step in the function design recipe is to write the function body.

There are at least three distinct algorithms, each of which will be subjected to top-down design. We’ll start by giving a high-level description of each. Each of these descriptions is the first step in doing a top-down design for that approach.

• Find, remove, find. Find the index of the minimum, remove it from the list, and find the index of the new minimum item in the list. After we have the second index, we need to put back the value we removed and, if necessary, adjust the second index to account for that removal and reinsertion.

• Sort, identify minimums, get indices. Sort the list, get the two smallest numbers, and then find their indices in the original list.

• Walk through the list. Examine each value in the list in order, keep track of the two smallest values found so far, and update these values when a new smaller value is found.

The first two algorithms mutate the list, either by removing an item or by sorting the list. It is vital that our algorithms put things back the way we found them, or the people who call our functions are going to be annoyed with us. The last two lines of the docstring checks this for us.

While you are investigating these algorithms in the next few pages, consider this question: Which one is the fastest?

Find, Remove, Find

Here is the algorithm again, rewritten with one instruction per line and explicitly discussing the parameter L:

To address the first step, Find the index of the minimum item in L, we skim the output produced by calling help(list) and find that there are no methods that do exactly that. We’ll refine it:

Those first two statements match Python functions and methods: min does the first, and list.index does the second. (There are other ways; for example, we could have written a loop to do the search.)

We see that list.remove does the third statement, and the refinement of “Find the index of the new minimum item in the list” is also straightforward.

Notice that we’ve left some of our English statements in as comments, which makes it easier to understand the problem that each chunk of code solves:

Since we removed the smallest item, we need to put it back where it was. Because removing a value affects the indices of the following values, we might need to add 1 to min2 if the smallest item came before the second-smallest item:

That’s enough refinement (finally!) to do it all in Python:

That seems like a lot of thought and care, and it is. However, even if you go right to code, you’ll have to think through all those steps. By writing them down first, you have a better chance of getting it right with a minimum amount of work.

Sort, Identify Minimums, Get Indices

Here is the second algorithm rewritten with one instruction per line:

That looks straightforward; we can use built-in function sorted, which returns a copy of the list with the items in order from smallest to largest. We could have used method list.sort to sort L, but that breaks a fundamental rule: never mutate the contents of parameters unless the docstring says to.

Now we can find the indices and return them the same way we did in find-remove-find:

Walk Through the List

Our last algorithm starts the same way as for the first two:

We’ll move the second line before the first one because it describes the whole process; it isn’t a single step. Also, when we see phrases like each value, we think of iteration; the third line is part of that iteration, so we’ll indent it:

Every loop has three parts: an initialization section to set up the variables we’ll need, a loop condition, and a loop body. Here, the initialization will set up min1 and min2, which will be the indices of the smallest two items encountered so far. A natural choice is to set them to the first two items of the list:

We can turn that first line into a couple lines of code; we’ve left our English version in as a comment:

We have a couple of choices now. We can iterate with a for loop over the values, a for loop over the indices, or a while loop over the indices. Since we’re trying to find indices and we want to look at all of the items in the list, we’ll use a for loop over the indices—and we’ll start at index 2 because we’ve examined the first two values already. At the same time, we’ll refine the statement in the body of the loop to mention min1 and min2.

Now for the body of the loop. We’ll pick apart “update min1 and/or min2 when a new smaller value is found.” Here are the possibilities:

• If L[i] is smaller than both min1 and min2, then we have a new smallest item; so min1 currently holds the second smallest, and min2 currently holds the third smallest. We need to update both of them.

• If L[i] is larger than min1 and smaller than min2, we have a new second smallest.

• If L[i] is larger than both, we skip it.

All of those are easily translated to Python; in fact, we don’t even need code for the “larger than both” case: