Using the tools we've seen so far. Our computer programs can only do one
thing at a time. We've used methods that seem to do more
than one thing at a time, though. For example, list.sort sorts a list of
numbers, and list.index finds the index of a value in the list.
We're going to now explore these searching and sorting algorithms.
It turns out that they're really interesting, and there are a ton of
versions both sorting and searching. We're going to start now by taking a look
at linear search where we examine items one by one in a list.
One, we call helpline method index in class list.
We see that it returns the first index of the value that we're searching for.
For example, if we have an L refer to the list with a, b, c, a, and d as strings.
And we ask for the index of the a, we get back zero.
We don't get back 3 because it returns the index of the first occurrence of the
value in the list. When we ask what the index of the string
c is, it tells us 2. And when we ask for the index of string
d, it tells us 4. Here's how method index works.
When it's looking for d, it first looks at index 0, then 1, then 2, then 3.
And then in index 4, and it finds what we're looking for and it returns that
index. Linear means arranged in a line.
And we're essentially looking along the line from the start to the end in the
list. Here's how we're going to draw lists for
the rest of this week. We're going to place the values inside
the list instead of drawing an arrow to the value outside the list.
This is to save clutter, to make our drawings a little bit more clean.
We'll also draw our index variables above the indices to which they refer.
Here, i refers to zero. If we're looking for, say value v, which
refers to a, d, then what we'll do is we'll say, hey, is that value at L at
index i? And if it is, then we're happy we
returned i. If it isn't as in the case we have here,
what we do is we will add 1 to i, making i prefer to 1 now.
Is the d index an i now? No, it isn't.
So, we'll 1 to i. How about now?
No. Okay, L at index i equal to d?
No, okay. How about now?
yes we've done it. L at index i is d.
And, so we have found the value we're looking for.
So, we will return i in our linear search function.
We'll need to decide what to do if the value we're looking for is not in the
list. For example, what if it refers to the
string? In that case, let's return at least one.
We're going to continue to explore linear search by writing a function that
implements it. This function picks a list and any
object, and returns the integer into the index of that object in the list.
Here's an example called where we search for 2, where 2 appears at index 0.
Here's another where we search for 5, which is at index 2.
And now, we'll search for a number that isn't in the list.
We should get back minus 1. And our description is return the index
of the first occurrence of v in L, or return minus 1 if v is not in L.
Now, we'll draw our list again in order to help us reason about this algorithm.
i starts off at zero. Here's the code for that.
We don't know yet when we're going to stop, so we'll leave the condition blank.
But we do know that we add 1 to i each time through the loop.
After a couple of iterations, we have this general picture, i is some index.
We know that v is not here. Now, let's look at what this looks like
after this loop is over. [SOUND] What if v was not anywhere in
this entire list? What value does i have?
Well, i is to the right of this dividing line that I've, I've drawn.
And in this situation, where the value is not anywhere in the list, i is going to
end up equal to the length of l. So, one way to stop this loop is for i to
reach the length of L. We therefore can continue as long as i is
not equal to the length of L. The other situation in which we can stop
is when L find v at index i. That means that as long as i is not the
length of L, and v is not equal to L at index i, I add 1 to i.
After the loop terminates, I can check to see if i is equal to the length of L, to
know whether v was not in the list. If it wasn't, I'll return minus 1.
Otherwise, that means that I found v and I can return i.
Our algorithms that we're dealing with are starting to get more complicated.
Drawing pictures like this can really help develop correct code the first time
we write it, which in the long run will save us a ton of time.
We can actually get our initialization, i gets 0, straight from this picture right
here. If I have my list and I need the v not
section here to be empty, that puts the line right there, and that puts i right
at index zero. This picture is called a loop invariant.
An invariant is something that doesn't change and this picture describes what's
happening inside the loop after any number of iterations.
Before index i, we did not see a v. We have not yet examined anything from
index i onward, and so we still need to search it.
Looping variants and pictures like these are going to play a big part in the rest
of the lectures this week.
