Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Well done!
You have completed Introduction to Algorithms!
You have completed Introduction to Algorithms!
Preview
There's more than one way to implement the binary search algorithm and in this video we take a look at a new concept called recursion.
Resources
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
I'm going to create a new file.
0:00
As always File > New File, and
0:02
we'll name this
recursive_binary_search.py.
0:06
Okay, so I'm going to add our
new implementation here, so
0:14
that we don't get rid of that
first implementation we wrote.
0:17
Let's call this new function
recursive_binary_search.
0:20
Unlike our previous implementation,
0:24
this version is going to behave slightly
differently in that it won't return
0:26
the index value of the target
element if it exists.
0:31
Instead, it will just return a true value
if it exist, and a false if it doesn't.
0:34
So recursive_binary_search,
and like before,
0:38
this is going to take a list,
it accepts a list,
0:43
and a target to look for in that list.
0:48
We'll start at the body of the function
by considering what happens if an empty
0:52
list is passed in.
0:57
In that case, we would return false.
0:58
So let's say if the length of the list,
which is one way to figure it out if it's
1:00
empty, if it's equal to 0,
then we'll return False.
1:04
Now you might be thinking that in
the previous version of binary_search,
1:08
we didn't care if the list was empty.
1:12
Well, we actually did, but
in a roundabout sort of way.
1:15
So in the previous version of
binary_search, our function had a loop,
1:18
and that loop condition was true when
first was less than or equal to last.
1:23
So as long as it's less than or
equal to last, we continue the loop.
1:28
Now if we have an empty list,
then first is greater than last, and
1:32
the loop would never execute and
we return none at the bottom.
1:36
So this is the same logic
we're implementing here,
1:40
we're just doing it in
a slightly different way.
1:43
If the list is not empty,
we'll implement an else clause.
1:45
Now here we'll calculate
the midpoint by dividing
1:50
the length of the list by 2 and
rounding down.
1:54
Again, there's no use of first and
last here.
1:58
So say len(list), and then using the floor
division operator we'll divide that by 2.
2:01
If the value at the midpoint,
which we'll check by saying if list
2:08
using subscript notation,
we'll say midpoint as the index.
2:13
Now if this value at the midpoint
is the same as the target,
2:18
then we'll go ahead and return True.
2:23
So far, this is more or less the same
except for the value that were returning.
2:26
Let me actually get rid of all that.
2:33
Okay, all right, so if this isn't
the case, let's implement an else clause.
2:38
Now here we have two situations.
2:43
So first, if the value at
the midpoint is less than the target,
2:44
so if value at midpoint
is less than the target,
2:50
then we're gonna do something new,
we're going to call this function again.
2:54
This recursive_binary_search function
that we're in the process of defining,
3:02
we're gonna call that again, and
3:06
we're going to give it the portion of
the list that we want to focus on.
3:08
In the previous version of binary search,
3:12
we moved the first value to point
to the value after the midpoint.
3:15
Now here, we're going to create a new list
using what is called a slice operation,
3:20
and create a sublist that starts
at midpoint plus one, and
3:26
goes all the way to the end.
3:29
We're going to specify the same
target as a search target,
3:31
and when this function call is
done we'll return the value.
3:35
So we'll say return.
3:39
The return is important.
3:40
Then we'll call this function again,
recursive_binary_search.
3:42
And this function takes a list.
3:48
And here, we are going to use that
subscript notation to perform a slice
3:49
operation by using two indexes,
A start and an end.
3:54
So we'll say our new list
that we're passing in,
3:57
needs to start at midpoint + 1.
4:00
And then,
we'll go all the way to the end, and
4:02
this is a Python syntatic sugar,
so to speak.
4:06
If I don't specify an end index, Python
knows to just go all the way to the end.
4:09
All right, so this is our new
list that we're working with.
4:13
And we need a target.
4:16
We'll just pass it through.
4:17
If you're confused bear with me.
4:19
Just like before,
we'll visualize this at the end.
4:21
Okay, we have another else case here.
4:24
And this is a scenario where the value at
the midpoint is greater than the target.
4:26
Which means we only care about the values
in the list from the start going up to
4:31
the midpoint.
4:36
Now in this case as well, we're going to
call the binary_search function again and
4:37
specify a new list to work with.
4:41
This time, the list is going
to start at the beginning, and
4:43
then go all the way up to the midpoint.
4:46
So it looks the same.
4:48
We'll say return recursive_binary_search.
4:49
We're gonna pass in a list here.
4:55
So if we just put a colon here,
without a start index, Python knows to
4:57
start at the beginning and we're going
to go all the way up to the midpoint.
5:02
The target here is the same.
5:08
And this is our new binary_search
function, so let's see if this works.
5:09
Actually, yes.
5:15
Down here, we'll make some space and
I'll define a verify function.
5:16
We're now gonna copy/paste the previous
one because we're not returning none or
5:22
an integer here.
5:26
So we'll verify the result that we pass
in and we'll say print("Target found: and
5:27
this is just going to say true or
false, whether we found it, okay?
5:33
So like before, we need a numbers list.
5:38
And we'll do something like 1, 2,
3, 4, all the way up to 8, okay?
5:41
And now let's test this out.
5:46
So we'll call our
recursive_binary_search function.
5:48
And we'll pass in the numbers list.
5:54
And the target here is 12.
5:58
We're gonna verify this.
6:01
Verify the result, make sure it works.
6:03
And then we'll call it again.
6:05
This time making sure that we give it
a target that is actually in the list.
6:07
So here we'll say 6 and
we'll verify this again.
6:11
Make sure you hit Cmd + S to save.
6:16
And then in the console below,
6:18
we're gonna type out Python
recursive_binary_search.py.
6:21
Run it and you'll see that we've
verified that search works.
6:26
While we can't verify the index
position of the target value,
6:30
which is a modification to how
our algorithm works, we can
6:33
guarantee by running across all valid
inputs that search works as intended.
6:37
So why write a different search algorithm
here, a different binary search algorithm?
6:42
And what's the different between
these two implementations anyway?
6:48
The different lies in these last four
lines of code that you see here.
6:51
We did something unusual here.
6:58
Now, before we get into this, a small word
of advice, this is a confusing topic,
7:00
and people get confused
by it all the time.
7:05
Don't worry, that doesn't make
you any less of a programmer.
7:08
In fact, I have trouble with it often,
and always look it up,
7:12
including when I made this video.
7:15
This version of binary search
is a recursive binary search.
7:17
A recursive function is
one that calls itself.
7:21
This is hard for
7:25
people to grasp sometimes because there's
few easy analogies that make sense.
7:26
But you can think of it
in sort of this way.
7:31
So let's say you have this book that
contains answers to multiplication
7:33
problems.
7:37
You're working on a problem and
you look up an answer.
7:38
In the book, the answer for your problem
says add 10 to the answer for problem 52.
7:41
Okay, so you look up problem 52 and
there it says,
7:49
add 12 to the answer for problem 85.
7:53
Well, then you go and look up
the answer to problem 85 and finally,
7:57
instead of redirecting you somewhere else,
that answers says 10.
8:00
So you take that 10 and
then you go back to problem 52.
8:04
Because remember, the answer for
8:08
problem 52 was to add 12 to the answer for
problem 85.
8:10
So you take that 10, and then you
now have the answer to problem 85,
8:14
so you add 10 to 12 to get 22.
8:19
Then you go back to your original problem
where it said to add 10 to the answer for
8:22
problem 52.
8:27
So you add 10 to 22 and you get 32
to end up with your final answer.
8:28
So that's a weird way of doing it but
this is an example of recursion.
8:32
The solution to your first look up in
the book was the value obtained by another
8:36
look up in the same book,
which was followed by yet
8:41
another look up in the same book.
8:44
The book told you to check the book
until you arrived at some base value.
8:46
Our function works in a similar manner.
8:51
So let's visualize this
with an example of list.
8:53
Like before, we have a 9 element
list here, with values 0 through 8.
8:57
The target we're searching for
is the value 8.
9:02
We'll check if the list is
empty by calling len on it.
9:05
This list is not empty, so
we go to the else clause.
9:09
Next we calculated the midpoint,
9/2 = 4.5,
9:12
rounded down is 4, so
our first midpoint value is 4.
9:16
We'll perform our first check, is the
value at the midpoint equal to the target?
9:20
Not true, so we go to our else clause.
9:25
We'll perform another check here.
9:28
Is the value at the midpoint
less than the target.
9:30
Now in our case, this is true.
9:33
Earlier when we evaluated this condition,
we simply changed the value of first.
9:35
Here we're going to call the recursive
binary search function again and
9:40
give it a new list to work with.
9:44
The list starts at midpoint plus one.
9:46
So at index position 5,
all the way to the end.
9:49
Notice that this call to
recursive binary search,
9:52
inside a recursive binary search
includes a return statement.
9:56
This is important and
we'll come back to that in a second.
10:01
So now we're back at the top of a new
call to recursive binary search
10:04
with effectively a new list,
although technically,
10:09
just a sub list of the first one.
10:13
The list here contains the numbers 6,
7, and 8.
10:15
Starting with the first check, the list
is not empty, so we move to the else.
10:20
The midpoint in this case, length of the
list, 3 divided by 2 rounded down is 1.
10:25
Is the value of the midpoint
equal to the target?
10:30
Well, the value at that position is 7,
so no.
10:34
In the else, we perform the first check.
10:37
Is the value at the midpoint
less than the target?
10:40
Indeed it is.
10:43
So we call recursive binary search
again and provide it a new list.
10:44
This list starts at midpoint plus one and
goes to the end.
10:49
So in this case,
that's a single-element list.
10:53
Since this is a new call to
a recursive binary search,
10:56
we start back up at the top.
11:00
Is the list empty?
11:03
No, the midpoint is 0.
11:04
Is the value at the midpoint
the same as the target?
11:05
It is, so now we can return True.
11:10
Remember a minute ago, I pointed out that
when we call recursive_binary_search
11:12
from inside the function itself,
it's preceded by a return statement.
11:17
That plays a pretty important role here.
11:21
So back to our visualization.
11:24
We start at the top, and
we call binary search with a new list.
11:26
But because that's got
a return statement before it,
11:30
what we're saying is, hey,
when you run binary search on this,
11:33
whatever value you get back,
return it to the function that called you.
11:37
Then at the second level we
call binary search again,
11:41
along with another return statement.
11:44
Like with the first call,
11:46
we're instructing the function to return
a value back to the code that called it.
11:48
At this level, we find the target so the
function returns true back to the caller.
11:53
But since this inner function was also
called by a function with instructions to
11:58
return, it keeps returning that
true value back up until we
12:03
reach the very first
function that called it.
12:06
Going back to our book of answers,
recursive binary search instructs itself
12:09
to keep working on the problem
until it has a concrete answer.
12:14
Once it does, it works its way backwards,
giving the answer to every
12:18
function that called it until
the original caller has an answer.
12:22
Now, like I said, at the beginning
this is pretty complicated, so
12:26
you should not be concerned
if this doesn't click.
12:30
Honestly, this is not one thing that
you're gonna walk away with knowing fully
12:33
how to understand recursion
after your first try.
12:37
I'm really not lying when I say I have
a pretty hard time with recursion.
12:39
Now before we move on,
I do want to point out one thing.
12:43
Even though the implementation of
recursion is harder to understand,
12:46
it is easier in this case to understand
how we arrive at the logarithmic run
12:51
time since we keep calling
the function with smaller lists.
12:56
Let's take a break here.
13:00
In the next video, let's talk a bit
more about recursion and why it matters
13:02
You need to sign up for Treehouse in order to download course files.
Sign upYou need to sign up for Treehouse in order to set up Workspace
Sign up