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 have an understanding of how linear search works conceptually let's implement it in code
Documentation
Language Implementations
For the implementation of linear search in other programming languages, check out the instruction step following this video.
If you want to continue with Python but don't have programming experience, check out our Beginning Python Track.
[MUSIC]
0:00
So far we've spent a lot
of time in theory, and
0:04
while these things are all important
things to know, you get a much
0:07
better understanding of how algorithms
work when you start writing some code.
0:10
As I mentioned earlier, we're going
to be writing Python code in this and
0:14
all subsequent algorithm courses.
0:19
If you do have programming experience but
in another language,
0:21
check the Notes section of this video for
an implementation in your language.
0:25
If you don't have any experience, I'll
try my best to explain as we go along.
0:29
On the video you're watching right now,
you should see a Launch Workspaces button.
0:34
We're going to use a Treehouse coding
environment, called Workspaces,
0:39
to write all of our code.
0:43
If you're familiar with using
Python in a local environment,
0:45
then feel free to keep doing so.
0:48
Workspaces is an in-browser coding
environment, and we'll take care of all
0:50
the setup and installation so you can
focus on just writing and evaluating code.
0:55
Workspaces is quite
straightforward to use.
1:00
On the left here,
we have a File Navigator pane,
1:03
which is currently empty since
we haven't created a new file.
1:06
On the top, we have an Editor
where we write all our code.
1:09
And then below that, we have a terminal,
or a command line prompt,
1:12
where we can execute
the scripts that we write.
1:16
Let's add a new file here.
1:19
So at the top, in the Editor area,
we're going to go to File > New File.
1:20
And we'll name this linear_search.py.
1:24
In here,
1:31
we're going to define our linear_search
algorithm as a stand-alone function.
1:32
We start with the keyword def, which
defines a function or a block of code.
1:37
And then we give it the name,
linear_search.
1:43
This function will accept two arguments.
1:47
First, the list we're searching through,
and
1:49
then the target value we're looking for.
1:52
Both of these arguments are enclosed
in a set of parentheses, and
1:55
there's no space between the name
of the function and the arguments.
1:59
After that, we have a colon.
2:02
Now, there might be
a bit of confusion here.
2:05
Since we already have this target value,
what are we searching for?
2:07
And like the game we
played at the beginning,
2:11
where John's job was to find the value,
in a true implementation of linear_search,
2:14
we're looking for the position in
the list where the value exists.
2:19
If the target is in the list,
then we return its position.
2:23
And since this is a list, that position
is going to be denoted by an index value.
2:27
Now, if the target is not found,
we're going to return None.
2:32
The choice of what to return in
the failure case may be different in other
2:35
implementations of linear_search.
2:39
You can return -1,
since that isn't typically an index value.
2:41
You can also raise an exception,
which is Python speak for
2:46
indicating an error occurred.
2:49
Now, I think for us,
2:51
the most straightforward value
we can return here is None.
2:52
Now, let's add a comment to clarify this,
so hit Enter to go to the next line.
2:55
And then we're going to
add three single quotes,
2:59
and then below that on the next line,
we'll say,
3:04
Returns the index position of
the target if found, else returns None.
3:10
And then on the next line,
we'll close off those three quotes.
3:17
This is called a docstring and is a Python
convention for documenting your code.
3:20
The linear_search algorithm is
a sequential algorithm that compares each
3:25
item in the list until
the target is found.
3:30
To iterate, or loop, or
walk through our list sequentially,
3:33
we're going to use a for loop.
3:38
Now, typically when iterating over a list
in Python, we would use a loop like this.
3:40
We'd say for item in list.
3:45
This assigns the value at each index
position to that local variable item.
3:48
We don't want this, though, since we
primarily care about the index position.
3:53
Instead, we're going to use the range
function in Python to create
3:58
a range of values that start at 0 and
end at the number of items in the list.
4:03
So we'll say, for i, i stands for
index here, in range,
4:08
starting at 0, and going all the way
up to the length of the list.
4:13
We can get the number of items in
the list using the len function.
4:19
Now, going back to our
talk on complexity and
4:23
how individual steps in an algorithm
can have its own run times,
4:26
this is a line of code that we
would have to be careful about.
4:29
Python keeps track of the length of
a list, so this function call here,
4:33
len(list), is a constant-time operation.
4:38
Now, if this were a naive implementation,
let's say we wrote the implementation
4:41
of the list, and we iterate over the list
every time we call this length function,
4:46
then we've already incurred a linear cost.
4:51
Okay, so once we have a range of values
that represent indexed positions in this
4:54
list, we're going to iterate
over that using the for loop and
4:59
assign each index value
to this local variable i.
5:02
Using this index value,
5:05
we can obtain the item at that position
using subscript notation on the list.
5:07
Now, this is also a constant-time
operation because the language says so.
5:12
So we'll do if list, so
once we have this value,
5:17
which we'll get by using subscript
notation, so we'll say list[i].
5:20
Once we have this value,
we'll check if it matches the target.
5:24
So if the value at i == target,
well, if it does,
5:27
then we'll return that index
value cuz we want the position.
5:32
And once we hit this return statement,
we're going to terminate our function.
5:37
If the entire for loop is executed, and
we don't hit this return statement,
5:40
then the target does
not exist in the list.
5:45
So at the bottom here,
we'll say return None.
5:47
Even though all the individual operations
in our algorithm run in constant time,
5:51
in the worst-case scenario this for
loop here will have to go through
5:56
the entire range of values and
read every single element in the list.
6:00
Therefore giving the algorithm a big old
value of N, or running in linear time.
6:05
Now, if you've written code before,
6:10
you've definitely written code like this a
number of times, and I bet you didn't know
6:12
that all along you were implementing what
is essentially a well-known algorithm.
6:16
So I hope this goes to show you
that algorithms are a pretty
6:20
approachable topic.
6:23
Like everything else,
this does get advanced, but
6:25
as long as you take things slow,
there's no reason for it to be impossible.
6:27
Remember that not any block of
code counts as an algorithm.
6:31
To be a proper implementation of
linear_search, this block of code must
6:35
return a value, must complete execution
in a finite amount of time, and
6:39
must output the same result every time for
a given input set.
6:44
So let's verify this with a small test.
6:48
Let's write a function called
verify that accepts an index value.
6:52
If the value is not None,
it prints the index position.
6:57
If it is None, it informs us that
the target was not found in the list.
7:00
So def verify, and
this is going to take an index value.
7:04
And we'll say, if index is not None,
7:09
then we'll print Target found at index.
7:15
Whoops, that's a colon here.
7:24
Index, else, that needs to go back.
7:27
There we go, else, we'll say,
7:33
Target not found in list.
7:37
Okay, using this function,
let's define a range of numbers now.
7:41
So this will be a list numbers, and
we'll just go from 1 to, let's say, 10.
7:44
Now, if you've written Python code before,
you know that I
7:57
can use a list comprehension to make this
easier, but we'll keep things simple.
8:00
We can now use our linear_search
function to search for
8:04
the position of a target
value in this list.
8:08
So we can say result = linear_search.
8:10
And we're going to pass
in the numbers list,
8:15
that's the one we're searching through.
8:17
And we want to look for
the position where the value 12 exists.
8:19
And then we'll verify this result.
8:23
If our algorithm worked correctly,
8:27
the verify function should inform
us that the target did not exist.
8:29
So make sure you save the file,
which you can do by going up to File, and
8:33
Save, or hitting Cmd+S.
8:37
And then below in the terminal, you're
gonna type out python linear_search,
8:39
or you can hit Tab and
it should auto-complete, linear_search.py.
8:45
As you can see, correct,
the target was not found in the list, so
8:51
the output of our script
is what we expect.
8:54
For a second task, let's search for
the value 6 in the list.
8:57
So you can copy this, Cmd+C to copy,
and then paste it again, and
9:01
we'll just change 12 here to 6.
9:05
And then come back down to the terminal,
9:08
hit the up arrow to execute the same
command again, and hit Enter.
9:10
You'll notice that I forgot to hit Save,
so it did not account for that new change.
9:14
We'll try that again, and there you'll
see that if it works correctly,
9:18
which it did,
the index should be number 5.
9:23
Run the program on your end, and
make sure everything works as expected.
9:26
Our algorithm returned a result in each
case, it executed in a finite time, and
9:30
the results were the ones we expect.
9:35
In the next video,
let's tackle binary search.
9:37
You need to sign up for Treehouse in order to download course files.
Sign up