Bummer! This is just a preview. You need to be signed in with a Basic account to view the entire video.
Start a free Basic trial
to watch this video
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

0:00
I'm going to create a new file.

0:02
As always File > New File, and

0:06
we'll name this recursive_binary_search.py.

0:14
Okay, so I'm going to add our new implementation here, so

0:17
that we don't get rid of that first implementation we wrote.

0:20
Let's call this new function recursive_binary_search.

0:24
Unlike our previous implementation,

0:26
this version is going to behave slightly differently in that it won't return

0:31
the index value of the target element if it exists.

0:34
Instead, it will just return a true value if it exist, and a false if it doesn't.

0:38
So recursive_binary_search, and like before,

0:43
this is going to take a list, it accepts a list,

0:48
and a target to look for in that list.

0:52
We'll start at the body of the function by considering what happens if an empty

0:57
list is passed in.

0:58
In that case, we would return false.

1:00
So let's say if the length of the list, which is one way to figure it out if it's

1:04
empty, if it's equal to 0, then we'll return False.

1:08
Now you might be thinking that in the previous version of binary_search,

1:12
we didn't care if the list was empty.

1:15
Well, we actually did, but in a roundabout sort of way.

1:18
So in the previous version of binary_search, our function had a loop,

1:23
and that loop condition was true when first was less than or equal to last.

1:28
So as long as it's less than or equal to last, we continue the loop.

1:32
Now if we have an empty list, then first is greater than last, and

1:36
the loop would never execute and we return none at the bottom.

1:40
So this is the same logic we're implementing here,

1:43
we're just doing it in a slightly different way.

1:45
If the list is not empty, we'll implement an else clause.

1:50
Now here we'll calculate the midpoint by dividing

1:54
the length of the list by 2 and rounding down.

1:58
Again, there's no use of first and last here.

2:01
So say len(list), and then using the floor division operator we'll divide that by 2.

2:08
If the value at the midpoint, which we'll check by saying if list

2:13
using subscript notation, we'll say midpoint as the index.

2:18
Now if this value at the midpoint is the same as the target,

2:23
then we'll go ahead and return True.

2:26
So far, this is more or less the same except for the value that were returning.

2:33
Let me actually get rid of all that.

2:38
Okay, all right, so if this isn't the case, let's implement an else clause.

2:43
Now here we have two situations.

2:44
So first, if the value at the midpoint is less than the target,

2:50
so if value at midpoint is less than the target,

2:54
then we're gonna do something new, we're going to call this function again.

3:02
This recursive_binary_search function that we're in the process of defining,

3:06
we're gonna call that again, and

3:08
we're going to give it the portion of the list that we want to focus on.

3:12
In the previous version of binary search,

3:15
we moved the first value to point to the value after the midpoint.

3:20
Now here, we're going to create a new list using what is called a slice operation,

3:26
and create a sublist that starts at midpoint plus one, and

3:29
goes all the way to the end.

3:31
We're going to specify the same target as a search target,

3:35
and when this function call is done we'll return the value.

3:39
So we'll say return.

3:40
The return is important.

3:42
Then we'll call this function again, recursive_binary_search.

3:48
And this function takes a list.

3:49
And here, we are going to use that subscript notation to perform a slice

3:54
operation by using two indexes, A start and an end.

3:57
So we'll say our new list that we're passing in,

4:00
needs to start at midpoint + 1.

4:02
And then, we'll go all the way to the end, and

4:06
this is a Python syntatic sugar, so to speak.

4:09
If I don't specify an end index, Python knows to just go all the way to the end.

4:13
All right, so this is our new list that we're working with.

4:16
And we need a target.

4:17
We'll just pass it through.

4:19
If you're confused bear with me.

4:21
Just like before, we'll visualize this at the end.

4:24
Okay, we have another else case here.

4:26
And this is a scenario where the value at the midpoint is greater than the target.

4:31
Which means we only care about the values in the list from the start going up to

4:36
the midpoint.

4:37
Now in this case as well, we're going to call the binary_search function again and

4:41
specify a new list to work with.

4:43
This time, the list is going to start at the beginning, and

4:46
then go all the way up to the midpoint.

4:48
So it looks the same.

4:49
We'll say return recursive_binary_search.

4:55
We're gonna pass in a list here.

4:57
So if we just put a colon here, without a start index, Python knows to

5:02
start at the beginning and we're going to go all the way up to the midpoint.

5:08
The target here is the same.

5:09
And this is our new binary_search function, so let's see if this works.

5:15
Actually, yes.

5:16
Down here, we'll make some space and I'll define a verify function.

5:22
We're now gonna copy/paste the previous one because we're not returning none or

5:26
an integer here.

5:27
So we'll verify the result that we pass in and we'll say print("Target found: and

5:33
this is just going to say true or false, whether we found it, okay?

5:38
So like before, we need a numbers list.

5:41
And we'll do something like 1, 2, 3, 4, all the way up to 8, okay?

5:46
And now let's test this out.

5:48
So we'll call our recursive_binary_search function.

5:54
And we'll pass in the numbers list.

5:58
And the target here is 12.

6:01
We're gonna verify this.

6:03
Verify the result, make sure it works.

6:05
And then we'll call it again.

6:07
This time making sure that we give it a target that is actually in the list.

6:11
So here we'll say 6 and we'll verify this again.

6:16
Make sure you hit Cmd + S to save.

6:18
And then in the console below,

6:21
we're gonna type out Python recursive_binary_search.py.

6:26
Run it and you'll see that we've verified that search works.

6:30
While we can't verify the index position of the target value,

6:33
which is a modification to how our algorithm works, we can

6:37
guarantee by running across all valid inputs that search works as intended.

6:42
So why write a different search algorithm here, a different binary search algorithm?

6:48
And what's the different between these two implementations anyway?

6:51
The different lies in these last four lines of code that you see here.

6:58
We did something unusual here.

7:00
Now, before we get into this, a small word of advice, this is a confusing topic,

7:05
and people get confused by it all the time.

7:08
Don't worry, that doesn't make you any less of a programmer.

7:12
In fact, I have trouble with it often, and always look it up,

7:15
including when I made this video.

7:17
This version of binary search is a recursive binary search.

7:21
A recursive function is one that calls itself.

7:25
This is hard for

7:26
people to grasp sometimes because there's few easy analogies that make sense.

7:31
But you can think of it in sort of this way.

7:33
So let's say you have this book that contains answers to multiplication

7:37
problems.

7:38
You're working on a problem and you look up an answer.

7:41
In the book, the answer for your problem says add 10 to the answer for problem 52.

7:49
Okay, so you look up problem 52 and there it says,

7:53
add 12 to the answer for problem 85.

7:57
Well, then you go and look up the answer to problem 85 and finally,

8:00
instead of redirecting you somewhere else, that answers says 10.

8:04
So you take that 10 and then you go back to problem 52.

8:08
Because remember, the answer for

8:10
problem 52 was to add 12 to the answer for problem 85.

8:14
So you take that 10, and then you now have the answer to problem 85,

8:19
so you add 10 to 12 to get 22.

8:22
Then you go back to your original problem where it said to add 10 to the answer for

8:27
problem 52.

8:28
So you add 10 to 22 and you get 32 to end up with your final answer.

8:32
So that's a weird way of doing it but this is an example of recursion.

8:36
The solution to your first look up in the book was the value obtained by another

8:41
look up in the same book, which was followed by yet

8:44
another look up in the same book.

8:46
The book told you to check the book until you arrived at some base value.

8:51
Our function works in a similar manner.

8:53
So let's visualize this with an example of list.

8:57
Like before, we have a 9 element list here, with values 0 through 8.

9:02
The target we're searching for is the value 8.

9:05
We'll check if the list is empty by calling len on it.

9:09
This list is not empty, so we go to the else clause.

9:12
Next we calculated the midpoint, 9/2 = 4.5,

9:16
rounded down is 4, so our first midpoint value is 4.

9:20
We'll perform our first check, is the value at the midpoint equal to the target?

9:25
Not true, so we go to our else clause.

9:28
We'll perform another check here.

9:30
Is the value at the midpoint less than the target.

9:33
Now in our case, this is true.

9:35
Earlier when we evaluated this condition, we simply changed the value of first.

9:40
Here we're going to call the recursive binary search function again and

9:44
give it a new list to work with.

9:46
The list starts at midpoint plus one.

9:49
So at index position 5, all the way to the end.

9:52
Notice that this call to recursive binary search,

9:56
inside a recursive binary search includes a return statement.

10:01
This is important and we'll come back to that in a second.

10:04
So now we're back at the top of a new call to recursive binary search

10:09
with effectively a new list, although technically,

10:13
just a sub list of the first one.

10:15
The list here contains the numbers 6, 7, and 8.

10:20
Starting with the first check, the list is not empty, so we move to the else.

10:25
The midpoint in this case, length of the list, 3 divided by 2 rounded down is 1.

10:30
Is the value of the midpoint equal to the target?

10:34
Well, the value at that position is 7, so no.

10:37
In the else, we perform the first check.

10:40
Is the value at the midpoint less than the target?

10:43
Indeed it is.

10:44
So we call recursive binary search again and provide it a new list.

10:49
This list starts at midpoint plus one and goes to the end.

10:53
So in this case, that's a singleelement list.

10:56
Since this is a new call to a recursive binary search,

11:00
we start back up at the top.

11:03
Is the list empty?

11:04
No, the midpoint is 0.

11:05
Is the value at the midpoint the same as the target?

11:10
It is, so now we can return True.

11:12
Remember a minute ago, I pointed out that when we call recursive_binary_search

11:17
from inside the function itself, it's preceded by a return statement.

11:21
That plays a pretty important role here.

11:24
So back to our visualization.

11:26
We start at the top, and we call binary search with a new list.

11:30
But because that's got a return statement before it,

11:33
what we're saying is, hey, when you run binary search on this,

11:37
whatever value you get back, return it to the function that called you.

11:41
Then at the second level we call binary search again,

11:44
along with another return statement.

11:46
Like with the first call,

11:48
we're instructing the function to return a value back to the code that called it.

11:53
At this level, we find the target so the function returns true back to the caller.

11:58
But since this inner function was also called by a function with instructions to

12:03
return, it keeps returning that true value back up until we

12:06
reach the very first function that called it.

12:09
Going back to our book of answers, recursive binary search instructs itself

12:14
to keep working on the problem until it has a concrete answer.

12:18
Once it does, it works its way backwards, giving the answer to every

12:22
function that called it until the original caller has an answer.

12:26
Now, like I said, at the beginning this is pretty complicated, so

12:30
you should not be concerned if this doesn't click.

12:33
Honestly, this is not one thing that you're gonna walk away with knowing fully

12:37
how to understand recursion after your first try.

12:39
I'm really not lying when I say I have a pretty hard time with recursion.

12:43
Now before we move on, I do want to point out one thing.

12:46
Even though the implementation of recursion is harder to understand,

12:51
it is easier in this case to understand how we arrive at the logarithmic run

12:56
time since we keep calling the function with smaller lists.

13:00
Let's take a break here.

13:02
In the next video, let's talk a bit more about recursion and why it matters
You need to sign up for Treehouse in order to download course files.
Sign up