Preview
Video Player
00:00
00:00
Recursive Binary Search
13:07There'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.
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