**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

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

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 up