The needle in the haystack
Systematically searching arrays
This is an ongoing series. Please check out the collection for the rest of the articles.
Last post, I asked you if you could find the biggest number in this array:
I also asked if you could provably and systematically find the biggest number in any array I give you. As I suggested last time, knowing the definition of an array doesn’t automatically make you an expert on how to use arrays. In this case, knowing how to find the biggest number in an array doesn’t immediately follow from knowing what an array is.
But knowing how is important. Let me illustrate a few examples. Imagine you’re a game designer; you’re writing the part of an online game that keeps track of the highest scores that players worldwide have ever achieved. After accessing the database, the program has an array of all of the high scores. How do you find the highest score in the array?
Or imagine you’re designing a stock trading program; you’re writing the part of the decision algorithm that, after making a list of how profitable each stock option is predicted to be, must pick the most profitable stock. How do you find the most profitable one in a list with thousands of items?
Finding the maximum number in an array comes up in so many places it would take several pages to describe them all. And it’s hard to imagine a task better suited to a computer over a human. Reading a huge list of numbers and trying to find the biggest one in it is a tedious chore for a human to perform, but a computer can search the list quickly and infallibly. Let’s try to break down the problem into manageable pieces so that we can communicate to a computer what we want it to do.
First, let’s take the simplest case: when an array has only one number in it. For instance, [5] is an array with just one element: 5. How do you determine which number in [5] is the biggest? Don’t overthink this one; it’s as straightforward as it gets. If an array has only one number, that number must be the biggest number in the array because there are no other numbers to choose from.
What about when the array has two elements? [4, 8] or [12, -19], for instance. Then we can compare the two numbers using our comparison instructions: <, >, etc. In fact, we can define an instruction that does just this:
- max(x, y): if (x > y) then (x) else (y)
The maximum, often abbreviated max, of two numbers is whichever number is greater than the other. Note that max(5, 7) is 7 and max(-5, -7) is -5 since -5 > -7. In other words, max returns which number is greater and positive numbers are always greater than negative numbers. I try to distinguish “greater” and “bigger” since bigger suggests bigger in an absolute sense, for which negative signs don’t matter. The stated goal of this post — to find the biggest number in an array — is a bit misleading then. Really, we’re finding the greatest number in an array. Of course, you could find the biggest number by changing the max instruction so that it considers -5 smaller than -7. If you’re not sure how to do this, try it out now or after reading this post since it’s good practice. I’ll post the answer and its explanation next time.
So max basically solves the problem with 2-element arrays; let’s say you have an array named a with 2 elements: [4, 10]. To get the first element, you can write a[0]. To get the second, a[1]. So plug both elements into max to find the greater of the two:
Because a is [4, 10], the answer is 10 since 10 > 4. Problem solved!
Except this only works for 2-element arrays. What about 3-element and 4-element arrays? What about 1000-element arrays? For a 3-element array, we could get away with using two max instructions, like this (assume this new 3-element array is also called a):
To see how this works, break it up into pieces. The first piece calls the max instruction with two values: a[0] and another call to max. So first we must evaluate the other call to max so we know what it returns. The other call is this:
This is basically the same as the code for the 2-element array, just with the indices shifted by one. It takes two elements of a, a[1] and a[2], and returns whichever is greater. Now for the tricky part: the result of this second, inner max is used as one of the values in the first, outer max. The outer max compares a[0] with whatever the inner max returns. So let’s suppose that a is [4, 2, 6]. Here’s how it plays out:
- The inner max is evaluated: a[1] is 2 and a[2] is 6, so 2 is compared to 6
- 6 is greater than 2 so 6 is returned
- The outer max is evaluated: a[0] is 4, so 4 is compared to 6, the result we just determined
- 6 is greater than 4 so 6 is returned, making the final answer 6
Depending on your background, the full code may look intractably confusing at first glance, but it’s important to see that when you break it down, it’s composed of simple, understandable parts. For now, don’t worry if you don’t know how to write code like this; just make sure you understand how to read code like this. Please read this section again if you don’t understand the 3-element code yet — you won’t understand what’s about to come if this part is unclear. It often helps to plug in examples: try [3, 5, 0] and [-15, -16, -17], for example.
You could find the greatest element in a 4-element array by adding another max instruction. In fact, you could keep adding max instructions over and over to find the greatest element in an array of any size. This would, however, be quite silly. For one thing, you would have to write different code for each array size. One instruction for 2-element arrays, another for 3-element, etc. Since you often don’t know the size of the arrays you’re working with ahead of time, this idea already fails as a general solution. But another important reason this idea fails is that it’s cumbersome. Why would we write a different instruction for every possible array size if we could write one instruction that works for every size? This idea is a central theme in computer science (and science in general, actually). Instead of duplicating work over and over for each slightly different circumstance, develop a method that works for many circumstances. Make the computer do the work for you!
Before trying to write this general method, let’s imagine what it will look like:
- greatest(a): returns the greatest number in the array a
Notice that the size of the array isn’t even mentioned. No matter how big or small a is, greatest will return the correct answer. Now to actually write it…
What we want to do is use max instructions over and over without having to actually write down each individual use. In the specific circumstance of finding the greatest element in a 3-element array, the code will ultimately consist of calling an outer max and an inner max but it will look more general than that. greatest will call max as many times as needed for the array it’s given; 3-element arrays require 2 calls to max, 4-element arrays require 3 calls to max, etc. Let’s handle the simple case first, when the array has only one element. Assume the array we’re working with is again called a:
As you might have noticed, I snuck in a new instruction: size. This instruction simply returns the size of the array it’s given. So size([4]) returns 1, since [4] has 1 element. size([4, 8, 9]) returns 3, since [4, 8, 9] has 3 elements. What does the above code do, then? First it checks to see if a has a size of 1. If a does have a size of 1 (as in, it has one element) then it simply returns the array’s only element, a[0]. If a does not have a size of 1 (as in, it has 0 elements or more than 1) then we must do something else, denoted by “…” in the code above (“…” is not actual code!). For now, we’re going to ignore the case in which a has 0 elements since dealing with it introduces some concepts we’re not yet familiar with. Let’s focus on what happens when the size of a is greater than 1.
We need a way to compare two elements of a, keep whichever element is greater, compare this greater element to the next element, and then repeat the process for each remaining element. Since that’s a mouthful, let’s use an analogy: a group of friends is trying to determine who is the tallest in the group. To start, all of the friends make a line, so that there is a first friend F0, a second friend F1, and third friend F2, etc. Next, F0 and F1 compare heights. Suppose F0 is taller than F1. Then F0 and F2 compare heights. Suppose F2 is taller than F0. Then F2 and F3 compare heights. The process continues until all friends have been compared. The key is that only the tallest friend keeps getting compared; if F1 isn’t as tall as F0, F1 can’t be the tallest friend and can thus be ignored in future comparisons.
To match this analogy, the code should look something like this:
The code begins exactly as last time. The only difference between then and now is that “…” has been replaced with
As before, if a has just 1 element, a[0] is returned and the instruction is done. Else, this new part of the code is evaluated. Unfortunately, “rest of a” is not valid in Cake but we’ll formalize that in a bit. First, let’s understand what this code is saying. Since the array a has more than 1 element, a must include at least 1 more element besides a[0]. Namely, a[1] must exist. Maybe a[2] exists, but we don’t know for sure since all we know is that a has more than 1 element. Let’s say a has 2 elements: [3, 4]. That means a[0] exists, a[1] exists, and that’s it. So greatest(rest of a) becomes greatest([4]). The whole else expression then becomes max(3, greatest([4])). The greatest number in [4] is 4, so the expression reduces to max(3, 4), which I hope you agree is 4.
But wait! If greatest calls itself, won’t the process last forever? greatest calling greatest calling greatest, on and on forever? No, because greatest([4]) doesn’t call greatest. That’s the key — since [4] has just 1 element, greatest([4]) returns 4 without even touching the other part of the code. All we need to do is formalize “rest of a” and we’re done. But don’t worry — I’m going to do another example to clarify what’s going on. This idea of calling greatest over and over is a big one and I don’t expect you to master it overnight. Just follow it step by step and try to understand how it plays out.
Before we move on, here’s the formal version of “rest of a”:
- rest(a): returns [a[1], a[2], a[3], etc.]
To phrase it naturally, rest(a) returns a new array with every element of a except a[0]. So if size(a) is 6, size(rest(a)) is 5. Calling rest on an array with 1 element returns the empty array, [ ]. To be clear, this new array — let’s call it b — starts at 0 just like a. So b[0] gets whatever is in a[1], and b[1] gets whatever is in a[2], and so on and so forth. b is just a with the first element lopped off and everything else shifted to make up for it.
Without further ado, here is the final version of the code (except for the case when a is an empty array, which we’ll get to later):
I’ve split the code into multiple lines for readability. Cake doesn’t care about spaces or newlines or tabs or anything like that; if you want to break code into multiple lines, that’s fine (just don’t split up words — “i f” is not “if” and “i” on one line and “f” on another isn’t “if” either). Let’s take a look at this final version. The first part is unchanged. If a has 1 element, return it. The else expression is what’s interesting. It compares the first element of a with the greatest element of the rest of a. So if a is [3, 4, 5], it compares 3 to the greatest element in [4, 5]. How does this code find the greatest element in [4, 5]? It calls itself — greatest — over and over, each time comparing two elements at a time, until a has just 1 element left; then it simply returns that element. No matter how big a is, greatest searches through every element, comparing the greatest element it’s found so far with the rest of the elements.
A good way to understand greatest more clearly is to examine it step-by-step. After that, I’ll show you a visualization of the steps to crystallize the idea in your mind. Let’s again suppose that a is [2, 4, 3, 1]:
Step 0 is what happens when you call greatest([2, 4, 3, 1]). Since the size of a is more than 1, the else expression gets evaluated, which means that greatest(rest([2, 4, 3, 1])) is evaluated. rest(2, 4, 3, 1) is [4, 3, 1], so the previous expression reduces to greatest([4, 3, 1]). We’re now at Step 1, which considers its a to be [4, 3, 1] — it has no idea that outside of it, the full, original a is [2, 4, 3, 1] and it doesn’t need to know that. All it cares about is the a you give it, which at Step 1 is [4, 3, 1]. Don’t be misled by the reuse of the term a. Each call to greatest creates a new version of a that is independent from its predecessor.
Step 1 proceeds much like Step 0. Since the size of a is still more than 1, greatest gets called again. rest([4, 3, 1]) returns [3, 1], so the next step — Step 2 — is greatest([3, 1]). Again, Step 2 is much like Step 1: the size of a remains greater than 1 so another call to greatest is in order. This time, greatest([1]) gets called since rest([3, 1]) is [1]. We’re now on Step 3, which is the crucial step. Now the size of a is 1, so the then expression gets called. The then expression is simple — it returns a[0], which at this point is 1 since a is just [1].
Now, at Step 4, we retrace our steps. Why, you ask? Because now that we’ve figured out the answer to greatest([1]) we need to plug this answer into the code that requested it. Step 2 is where greatest([1]) was called so we jump back to this point in the process — except now we know the answer. Step 4 is just returning to Step 2 with the answer in hand. More explicitly, Step 2 evaluates max(a[0], greatest([1])). At Step 2, a[0] is 3. This means that we can reduce this expression to max(3, greatest([1])). So now that we’ve finished computing greatest([1]), we can plug in the answer. The answer to greatest([1]) is 1 so let’s plug it in to produce max(3, 1). 3 is greater than 1, so we return 3 and return one step higher in the process.
One step higher returns us to the code at Step 1, except this time we have the answer. So Step 5 answers the problem initially proposed in Step 1. Step 1 wants to know max(a[0], greatest([3, 1]). We know that at this point, a[0] is 4. We also just found the answer to greatest([3, 1]) in the previous step, Step 4, so we can just plug that in to get max(4, 3). 4 is greater than 3, so we return 4 and return one step higher in the process.
We’re now returning to the initial step, Step 0. This time, however, we know the answer to greatest([4, 3, 1]) — it’s 4. So we can take a[0], which at Step 0 is 2, and combine that with our answer to greatest([4, 3, 1]), which is 4, to get the final answer to the initial question: max(a[0], greatest([2, 4, 3, 1])). Plugging in the answers, this reduces to max(2, 4) which is 4. Thus, the answer to greatest([2, 4, 3, 1]) is 4.
Let’s visualize this (the GIF loops, so wait for Step 0):
I hope the step-by-step explanation and its visualization made things a bit clearer. The idea we’ve been exploring is called recursion, which is when an instruction calls itself over and over with different values in order to eventually construct a final answer. greatest is recursive because it calls itself to get the answer. The key to building a recursive instruction is to have a base case, which is the case (or situation) in which the instruction doesn’t call itself. Without a base case, the instruction would call itself without end, which is obviously a major problem. The base case of greatest comes when it checks whether the size of a equals 1. If it is, greatest stops calling itself and just returns the first element of a. Else, it keeps calling itself until it has searched through all of its elements. No matter how many elements are in a, greatest keeps checking until it reaches the end — the final element of a — and then backtracks, using the answers it finds in later steps to solve questions posed in previous steps. When Step 0 asks for the result of greatest([4, 3, 1]), greatest keeps calling itself until it comes back with the answer. This answer is plugged in, and the code moves on.
We’re going to talk a lot more about recursion, but first we’re going to cover a bit more concerning arrays and then move on to strings. No, not rope or thread. A string in computer science is much like the everyday term “word”, which here means a series of letters, numbers, symbols, characters, etc. One might even say that a string is an array of characters. But I’m getting ahead of myself. For now, just try to wrap your mind around recursion and enjoy the stock photo of string (twine, to be specific).
Here’s each frame of the visualization GIF:
