Preview
Video Player
00:00
00:00
Linear Search in Code
9:40Now that we have an understanding of how linear search works conceptually let's implement it in code
[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