1
00:00:00,220 --> 00:00:02,624
I'm going to create a new file.

2
00:00:02,624 --> 00:00:06,966
As always File > New File, and

3
00:00:06,966 --> 00:00:14,482
we'll name this
recursive_binary_search.py.

4
00:00:14,482 --> 00:00:17,519
Okay, so I'm going to add our
new implementation here, so

5
00:00:17,519 --> 00:00:20,698
that we don't get rid of that
first implementation we wrote.

6
00:00:20,698 --> 00:00:24,198
Let's call this new function
recursive_binary_search.

7
00:00:24,198 --> 00:00:26,508
Unlike our previous implementation,

8
00:00:26,508 --> 00:00:31,058
this version is going to behave slightly
differently in that it won't return

9
00:00:31,058 --> 00:00:34,072
the index value of the target
element if it exists.

10
00:00:34,072 --> 00:00:38,560
Instead, it will just return a true value
if it exist, and a false if it doesn't.

11
00:00:38,560 --> 00:00:43,799
So recursive_binary_search,
and like before,

12
00:00:43,799 --> 00:00:48,560
this is going to take a list,
it accepts a list,

13
00:00:48,560 --> 00:00:52,262
and a target to look for in that list.

14
00:00:52,262 --> 00:00:57,131
We'll start at the body of the function
by considering what happens if an empty

15
00:00:57,131 --> 00:00:58,329
list is passed in.

16
00:00:58,329 --> 00:01:00,245
In that case, we would return false.

17
00:01:00,245 --> 00:01:04,934
So let's say if the length of the list,
which is one way to figure it out if it's

18
00:01:04,934 --> 00:01:08,358
empty, if it's equal to 0,
then we'll return False.

19
00:01:08,358 --> 00:01:12,925
Now you might be thinking that in
the previous version of binary_search,

20
00:01:12,925 --> 00:01:15,254
we didn't care if the list was empty.

21
00:01:15,254 --> 00:01:18,779
Well, we actually did, but
in a roundabout sort of way.

22
00:01:18,779 --> 00:01:23,843
So in the previous version of
binary_search, our function had a loop,

23
00:01:23,843 --> 00:01:28,999
and that loop condition was true when
first was less than or equal to last.

24
00:01:28,999 --> 00:01:32,681
So as long as it's less than or
equal to last, we continue the loop.

25
00:01:32,681 --> 00:01:36,845
Now if we have an empty list,
then first is greater than last, and

26
00:01:36,845 --> 00:01:40,800
the loop would never execute and
we return none at the bottom.

27
00:01:40,800 --> 00:01:43,353
So this is the same logic
we're implementing here,

28
00:01:43,353 --> 00:01:45,798
we're just doing it in
a slightly different way.

29
00:01:45,798 --> 00:01:50,117
If the list is not empty,
we'll implement an else clause.

30
00:01:50,117 --> 00:01:54,472
Now here we'll calculate
the midpoint by dividing

31
00:01:54,472 --> 00:01:58,427
the length of the list by 2 and
rounding down.

32
00:01:58,427 --> 00:02:01,991
Again, there's no use of first and
last here.

33
00:02:01,991 --> 00:02:08,213
So say len(list), and then using the floor
division operator we'll divide that by 2.

34
00:02:08,213 --> 00:02:13,518
If the value at the midpoint,
which we'll check by saying if list

35
00:02:13,518 --> 00:02:18,645
using subscript notation,
we'll say midpoint as the index.

36
00:02:18,645 --> 00:02:23,409
Now if this value at the midpoint
is the same as the target,

37
00:02:23,409 --> 00:02:26,532
then we'll go ahead and return True.

38
00:02:26,532 --> 00:02:33,416
So far, this is more or less the same
except for the value that were returning.

39
00:02:33,416 --> 00:02:36,634
Let me actually get rid of all that.

40
00:02:38,354 --> 00:02:43,432
Okay, all right, so if this isn't
the case, let's implement an else clause.

41
00:02:43,432 --> 00:02:44,955
Now here we have two situations.

42
00:02:44,955 --> 00:02:50,664
So first, if the value at
the midpoint is less than the target,

43
00:02:50,664 --> 00:02:54,973
so if value at midpoint
is less than the target,

44
00:02:54,973 --> 00:03:02,218
then we're gonna do something new,
we're going to call this function again.

45
00:03:02,218 --> 00:03:06,924
This recursive_binary_search function
that we're in the process of defining,

46
00:03:06,924 --> 00:03:08,845
we're gonna call that again, and

47
00:03:08,845 --> 00:03:12,771
we're going to give it the portion of
the list that we want to focus on.

48
00:03:12,771 --> 00:03:15,741
In the previous version of binary search,

49
00:03:15,741 --> 00:03:20,289
we moved the first value to point
to the value after the midpoint.

50
00:03:20,289 --> 00:03:26,000
Now here, we're going to create a new list
using what is called a slice operation,

51
00:03:26,000 --> 00:03:29,998
and create a sublist that starts
at midpoint plus one, and

52
00:03:29,998 --> 00:03:31,890
goes all the way to the end.

53
00:03:31,890 --> 00:03:35,563
We're going to specify the same
target as a search target,

54
00:03:35,563 --> 00:03:39,315
and when this function call is
done we'll return the value.

55
00:03:39,315 --> 00:03:40,935
So we'll say return.

56
00:03:40,935 --> 00:03:42,515
The return is important.

57
00:03:42,515 --> 00:03:48,121
Then we'll call this function again,
recursive_binary_search.

58
00:03:48,121 --> 00:03:49,921
And this function takes a list.

59
00:03:49,921 --> 00:03:54,396
And here, we are going to use that
subscript notation to perform a slice

60
00:03:54,396 --> 00:03:57,689
operation by using two indexes,
A start and an end.

61
00:03:57,689 --> 00:04:00,783
So we'll say our new list
that we're passing in,

62
00:04:00,783 --> 00:04:02,855
needs to start at midpoint + 1.

63
00:04:02,855 --> 00:04:06,040
And then,
we'll go all the way to the end, and

64
00:04:06,040 --> 00:04:09,246
this is a Python syntatic sugar,
so to speak.

65
00:04:09,246 --> 00:04:13,901
If I don't specify an end index, Python
knows to just go all the way to the end.

66
00:04:13,901 --> 00:04:16,527
All right, so this is our new
list that we're working with.

67
00:04:16,527 --> 00:04:17,999
And we need a target.

68
00:04:17,999 --> 00:04:19,687
We'll just pass it through.

69
00:04:19,687 --> 00:04:21,192
If you're confused bear with me.

70
00:04:21,192 --> 00:04:24,022
Just like before,
we'll visualize this at the end.

71
00:04:24,022 --> 00:04:26,822
Okay, we have another else case here.

72
00:04:26,822 --> 00:04:31,762
And this is a scenario where the value at
the midpoint is greater than the target.

73
00:04:31,762 --> 00:04:36,690
Which means we only care about the values
in the list from the start going up to

74
00:04:36,690 --> 00:04:37,702
the midpoint.

75
00:04:37,702 --> 00:04:41,995
Now in this case as well, we're going to
call the binary_search function again and

76
00:04:41,995 --> 00:04:43,634
specify a new list to work with.

77
00:04:43,634 --> 00:04:46,809
This time, the list is going
to start at the beginning, and

78
00:04:46,809 --> 00:04:48,853
then go all the way up to the midpoint.

79
00:04:48,853 --> 00:04:49,653
So it looks the same.

80
00:04:49,653 --> 00:04:55,933
We'll say return recursive_binary_search.

81
00:04:55,933 --> 00:04:57,773
We're gonna pass in a list here.

82
00:04:57,773 --> 00:05:02,835
So if we just put a colon here,
without a start index, Python knows to

83
00:05:02,835 --> 00:05:08,360
start at the beginning and we're going
to go all the way up to the midpoint.

84
00:05:08,360 --> 00:05:09,294
The target here is the same.

85
00:05:09,294 --> 00:05:15,432
And this is our new binary_search
function, so let's see if this works.

86
00:05:15,432 --> 00:05:16,892
Actually, yes.

87
00:05:16,892 --> 00:05:22,287
Down here, we'll make some space and
I'll define a verify function.

88
00:05:22,287 --> 00:05:26,980
We're now gonna copy/paste the previous
one because we're not returning none or

89
00:05:26,980 --> 00:05:27,994
an integer here.

90
00:05:27,994 --> 00:05:33,948
So we'll verify the result that we pass
in and we'll say print("Target found: and

91
00:05:33,948 --> 00:05:38,679
this is just going to say true or
false, whether we found it, okay?

92
00:05:38,679 --> 00:05:41,585
So like before, we need a numbers list.

93
00:05:41,585 --> 00:05:46,949
And we'll do something like 1, 2,
3, 4, all the way up to 8, okay?

94
00:05:46,949 --> 00:05:48,645
And now let's test this out.

95
00:05:48,645 --> 00:05:54,996
So we'll call our
recursive_binary_search function.

96
00:05:54,996 --> 00:05:58,150
And we'll pass in the numbers list.

97
00:05:58,150 --> 00:06:01,561
And the target here is 12.

98
00:06:01,561 --> 00:06:03,910
We're gonna verify this.

99
00:06:03,910 --> 00:06:05,760
Verify the result, make sure it works.

100
00:06:05,760 --> 00:06:07,230
And then we'll call it again.

101
00:06:07,230 --> 00:06:11,030
This time making sure that we give it
a target that is actually in the list.

102
00:06:11,030 --> 00:06:16,280
So here we'll say 6 and
we'll verify this again.

103
00:06:16,280 --> 00:06:18,520
Make sure you hit Cmd + S to save.

104
00:06:18,520 --> 00:06:21,206
And then in the console below,

105
00:06:21,206 --> 00:06:26,900
we're gonna type out Python
recursive_binary_search.py.

106
00:06:26,900 --> 00:06:30,116
Run it and you'll see that we've
verified that search works.

107
00:06:30,116 --> 00:06:33,920
While we can't verify the index
position of the target value,

108
00:06:33,920 --> 00:06:37,436
which is a modification to how
our algorithm works, we can

109
00:06:37,436 --> 00:06:42,130
guarantee by running across all valid
inputs that search works as intended.

110
00:06:42,130 --> 00:06:48,385
So why write a different search algorithm
here, a different binary search algorithm?

111
00:06:48,385 --> 00:06:51,345
And what's the different between
these two implementations anyway?

112
00:06:51,345 --> 00:06:58,170
The different lies in these last four
lines of code that you see here.

113
00:06:58,170 --> 00:07:00,725
We did something unusual here.

114
00:07:00,725 --> 00:07:05,693
Now, before we get into this, a small word
of advice, this is a confusing topic,

115
00:07:05,693 --> 00:07:08,295
and people get confused
by it all the time.

116
00:07:08,295 --> 00:07:12,005
Don't worry, that doesn't make
you any less of a programmer.

117
00:07:12,005 --> 00:07:15,336
In fact, I have trouble with it often,
and always look it up,

118
00:07:15,336 --> 00:07:17,209
including when I made this video.

119
00:07:17,209 --> 00:07:21,955
This version of binary search
is a recursive binary search.

120
00:07:21,955 --> 00:07:25,465
A recursive function is
one that calls itself.

121
00:07:25,465 --> 00:07:26,495
This is hard for

122
00:07:26,495 --> 00:07:31,891
people to grasp sometimes because there's
few easy analogies that make sense.

123
00:07:31,891 --> 00:07:33,591
But you can think of it
in sort of this way.

124
00:07:33,591 --> 00:07:37,984
So let's say you have this book that
contains answers to multiplication

125
00:07:37,984 --> 00:07:38,710
problems.

126
00:07:38,710 --> 00:07:41,980
You're working on a problem and
you look up an answer.

127
00:07:41,980 --> 00:07:49,129
In the book, the answer for your problem
says add 10 to the answer for problem 52.

128
00:07:49,129 --> 00:07:53,560
Okay, so you look up problem 52 and
there it says,

129
00:07:53,560 --> 00:07:57,002
add 12 to the answer for problem 85.

130
00:07:57,002 --> 00:08:00,902
Well, then you go and look up
the answer to problem 85 and finally,

131
00:08:00,902 --> 00:08:04,880
instead of redirecting you somewhere else,
that answers says 10.

132
00:08:04,880 --> 00:08:08,407
So you take that 10 and
then you go back to problem 52.

133
00:08:08,407 --> 00:08:10,711
Because remember, the answer for

134
00:08:10,711 --> 00:08:14,689
problem 52 was to add 12 to the answer for
problem 85.

135
00:08:14,689 --> 00:08:19,745
So you take that 10, and then you
now have the answer to problem 85,

136
00:08:19,745 --> 00:08:22,208
so you add 10 to 12 to get 22.

137
00:08:22,208 --> 00:08:27,108
Then you go back to your original problem
where it said to add 10 to the answer for

138
00:08:27,108 --> 00:08:28,060
problem 52.

139
00:08:28,060 --> 00:08:32,720
So you add 10 to 22 and you get 32
to end up with your final answer.

140
00:08:32,720 --> 00:08:36,927
So that's a weird way of doing it but
this is an example of recursion.

141
00:08:36,927 --> 00:08:41,721
The solution to your first look up in
the book was the value obtained by another

142
00:08:41,721 --> 00:08:44,817
look up in the same book,
which was followed by yet

143
00:08:44,817 --> 00:08:46,903
another look up in the same book.

144
00:08:46,903 --> 00:08:51,723
The book told you to check the book
until you arrived at some base value.

145
00:08:51,723 --> 00:08:53,880
Our function works in a similar manner.

146
00:08:53,880 --> 00:08:57,280
So let's visualize this
with an example of list.

147
00:08:57,280 --> 00:09:02,464
Like before, we have a 9 element
list here, with values 0 through 8.

148
00:09:02,464 --> 00:09:05,902
The target we're searching for
is the value 8.

149
00:09:05,902 --> 00:09:09,543
We'll check if the list is
empty by calling len on it.

150
00:09:09,543 --> 00:09:12,250
This list is not empty, so
we go to the else clause.

151
00:09:12,250 --> 00:09:16,502
Next we calculated the midpoint,
9/2 = 4.5,

152
00:09:16,502 --> 00:09:20,854
rounded down is 4, so
our first midpoint value is 4.

153
00:09:20,854 --> 00:09:25,688
We'll perform our first check, is the
value at the midpoint equal to the target?

154
00:09:25,688 --> 00:09:28,035
Not true, so we go to our else clause.

155
00:09:28,035 --> 00:09:30,388
We'll perform another check here.

156
00:09:30,388 --> 00:09:33,560
Is the value at the midpoint
less than the target.

157
00:09:33,560 --> 00:09:35,376
Now in our case, this is true.

158
00:09:35,376 --> 00:09:40,266
Earlier when we evaluated this condition,
we simply changed the value of first.

159
00:09:40,266 --> 00:09:44,719
Here we're going to call the recursive
binary search function again and

160
00:09:44,719 --> 00:09:46,619
give it a new list to work with.

161
00:09:46,619 --> 00:09:49,164
The list starts at midpoint plus one.

162
00:09:49,164 --> 00:09:52,403
So at index position 5,
all the way to the end.

163
00:09:52,403 --> 00:09:56,220
Notice that this call to
recursive binary search,

164
00:09:56,220 --> 00:10:01,023
inside a recursive binary search
includes a return statement.

165
00:10:01,023 --> 00:10:04,489
This is important and
we'll come back to that in a second.

166
00:10:04,489 --> 00:10:09,377
So now we're back at the top of a new
call to recursive binary search

167
00:10:09,377 --> 00:10:13,395
with effectively a new list,
although technically,

168
00:10:13,395 --> 00:10:15,776
just a sub list of the first one.

169
00:10:15,776 --> 00:10:20,050
The list here contains the numbers 6,
7, and 8.

170
00:10:20,050 --> 00:10:25,335
Starting with the first check, the list
is not empty, so we move to the else.

171
00:10:25,335 --> 00:10:30,643
The midpoint in this case, length of the
list, 3 divided by 2 rounded down is 1.

172
00:10:30,643 --> 00:10:34,155
Is the value of the midpoint
equal to the target?

173
00:10:34,155 --> 00:10:37,935
Well, the value at that position is 7,
so no.

174
00:10:37,935 --> 00:10:40,615
In the else, we perform the first check.

175
00:10:40,615 --> 00:10:43,735
Is the value at the midpoint
less than the target?

176
00:10:43,735 --> 00:10:44,895
Indeed it is.

177
00:10:44,895 --> 00:10:49,110
So we call recursive binary search
again and provide it a new list.

178
00:10:49,110 --> 00:10:53,168
This list starts at midpoint plus one and
goes to the end.

179
00:10:53,168 --> 00:10:56,068
So in this case,
that's a single-element list.

180
00:10:56,068 --> 00:11:00,954
Since this is a new call to
a recursive binary search,

181
00:11:00,954 --> 00:11:03,459
we start back up at the top.

182
00:11:03,459 --> 00:11:04,123
Is the list empty?

183
00:11:04,123 --> 00:11:05,503
No, the midpoint is 0.

184
00:11:05,503 --> 00:11:10,173
Is the value at the midpoint
the same as the target?

185
00:11:10,173 --> 00:11:12,258
It is, so now we can return True.

186
00:11:12,258 --> 00:11:17,368
Remember a minute ago, I pointed out that
when we call recursive_binary_search

187
00:11:17,368 --> 00:11:21,894
from inside the function itself,
it's preceded by a return statement.

188
00:11:21,894 --> 00:11:24,534
That plays a pretty important role here.

189
00:11:24,534 --> 00:11:26,826
So back to our visualization.

190
00:11:26,826 --> 00:11:30,714
We start at the top, and
we call binary search with a new list.

191
00:11:30,714 --> 00:11:33,763
But because that's got
a return statement before it,

192
00:11:33,763 --> 00:11:37,407
what we're saying is, hey,
when you run binary search on this,

193
00:11:37,407 --> 00:11:41,469
whatever value you get back,
return it to the function that called you.

194
00:11:41,469 --> 00:11:44,653
Then at the second level we
call binary search again,

195
00:11:44,653 --> 00:11:46,994
along with another return statement.

196
00:11:46,994 --> 00:11:48,474
Like with the first call,

197
00:11:48,474 --> 00:11:53,129
we're instructing the function to return
a value back to the code that called it.

198
00:11:53,129 --> 00:11:58,673
At this level, we find the target so the
function returns true back to the caller.

199
00:11:58,673 --> 00:12:03,413
But since this inner function was also
called by a function with instructions to

200
00:12:03,413 --> 00:12:06,950
return, it keeps returning that
true value back up until we

201
00:12:06,950 --> 00:12:09,729
reach the very first
function that called it.

202
00:12:09,729 --> 00:12:14,669
Going back to our book of answers,
recursive binary search instructs itself

203
00:12:14,669 --> 00:12:18,628
to keep working on the problem
until it has a concrete answer.

204
00:12:18,628 --> 00:12:22,704
Once it does, it works its way backwards,
giving the answer to every

205
00:12:22,704 --> 00:12:26,588
function that called it until
the original caller has an answer.

206
00:12:26,588 --> 00:12:30,387
Now, like I said, at the beginning
this is pretty complicated, so

207
00:12:30,387 --> 00:12:33,331
you should not be concerned
if this doesn't click.

208
00:12:33,331 --> 00:12:37,223
Honestly, this is not one thing that
you're gonna walk away with knowing fully

209
00:12:37,223 --> 00:12:39,734
how to understand recursion
after your first try.

210
00:12:39,734 --> 00:12:43,867
I'm really not lying when I say I have
a pretty hard time with recursion.

211
00:12:43,867 --> 00:12:46,680
Now before we move on,
I do want to point out one thing.

212
00:12:46,680 --> 00:12:51,519
Even though the implementation of
recursion is harder to understand,

213
00:12:51,519 --> 00:12:56,517
it is easier in this case to understand
how we arrive at the logarithmic run

214
00:12:56,517 --> 00:13:00,644
time since we keep calling
the function with smaller lists.

215
00:13:00,644 --> 00:13:02,296
Let's take a break here.

216
00:13:02,296 --> 00:13:07,113
In the next video, let's talk a bit
more about recursion and why it matters