Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Preview
Start a free Courses trial
to watch this video
Now that we've covered sorting algorithms, the groundwork has been laid to talk about searching algorithms.
See the instruction step following this video for the code!
[MUSIC]
0:00
[SOUND] Now that we've
covered sorting algorithms,
0:04
the groundwork has been laid to
talk about searching algorithms.
0:07
If you need to search through
an unsorted list of items,
0:10
binary search isn't an option
because you have no idea which half
0:13
of the list contains
the item you're looking for.
0:17
Your only real option is to
start at the beginning and
0:20
compare each item in the list
to your target value,
0:23
one at a time until you find
the value you're looking for.
0:25
This algorithm is called linear_search or
sequential search,
0:29
because the search proceeds in
a straight line or sequence.
0:33
Even though linear_search is inefficient,
searching for just one name will happen so
0:36
fast that we won't be able to tell
anything useful about the algorithm's
0:40
runtime.
0:44
So let's suppose we add
100 different names and
0:45
that we needed to know where they
appear in a list of unsorted names.
0:47
Here is some code that demonstrates.
0:51
As usual, this code at the top isn't
relevant to the search algorithm.
0:53
It's just like the code that loaded
the list of numbers from a file in
0:57
the previous stage, but this code calls
a different function, load_strings,
1:00
that loads a list of strings in.
1:05
If you want the load_strings Python code,
we'll have it for
1:06
you in the teacher's notes.
1:10
Here's a separate hard-coded list,
1:11
containing the 100 names
we're going to search for.
1:13
We'll loop through each name in this list
and pass it to our search function to get
1:16
the index within the full
list where it appears.
1:20
Now, let's implement the search function.
1:23
Compared to the sorting algorithms,
this is going to be short.
1:25
The index of item function takes the
Python list you want to search through and
1:29
a single target value
you want to search for.
1:33
Now we need to loop over
each item in the list.
1:36
The range function gives us a range of
numbers from its first argument up to, but
1:39
not including, its second argument.
1:43
So if our list had a length of five,
1:46
this would loop over
the indexes zero through four.
1:47
We test whether the list item at
the current index matches our target.
1:51
If it does, then we return
the index of the current item.
1:56
This will exit the index of item function
without looping over the remaining items
1:59
In the list.
2:03
If we reach the end of the loop
without finding the target value,
2:04
that means that it wasn't in the list.
2:08
So instead of returning an index,
2:09
we return the special Python value, None,
which indicates the absence of a value.
2:11
Other languages have similar values,
like nil or null.
2:17
But if yours doesn't, you might have to
return a value that would otherwise be
2:20
impossible, like an index of negative one.
2:23
Now let's call our new search function.
2:26
We start by looping over the list
of 100 values we're looking for.
2:28
We're using the values themselves this
time, not their indexes within the list,
2:32
so there's no need to mess
with Python's range function.
2:36
Here's the actual call to
the index_of_item function.
2:40
We pass it the full list of names
that we loaded from the file
2:43
plus the name we want to search for
within that list.
2:46
Then we store the index
it returns in a variable.
2:48
And lastly, we print the index we get
back from the index_of_item function.
2:52
Let's save this and
go to our console and see if it works.
2:56
python linear_search.pi
names/unsorted.txt.
3:00
And it'll print out the list
of indexes for each name.
3:09
I actually set it up so that the last two
items in the list of names we're going to
3:13
search for corresponded to the first and
last name within the file.
3:17
So if we open up our unsorted.txt file,
3:21
we'll see Mary Rosenberger as the first
name and Alonso Viviano as the last name.
3:23
And those are the last two values in
our list of names we're searching for.
3:31
So it returned an index of 0 for
that second-to-last name, and
3:35
you can see that name here
on line 1 of the file.
3:39
The line numbering starts at 1, and
the Python list indexes start at 0, so
3:42
that makes sense.
3:46
And for the last name,
we'll return an index of 109873.
3:48
And you can see that
name here on line 109874.
3:54
So we can see that it's
returning the correct indexes.
3:58
But right now, we're just searching for
4:01
100 different names in
a list of 100,000 names.
4:03
In the real world,
we're going to be looking for
4:06
many more names than that within
much bigger lists than that.
4:08
Can we do this any faster?
4:11
Yes, but we'll need to use
the binary search algorithm.
4:13
And for that to work,
we need to sort our list of strings.
4:17
We'll do that in the next video.
4:20
You need to sign up for Treehouse in order to download course files.
Sign up