1
00:00:00,500 --> 00:00:01,430
Welcome back.

2
00:00:01,430 --> 00:00:05,630
So this is the iterative version of the binary search which we have already written.

3
00:00:05,660 --> 00:00:09,680
Now let's go ahead and code the recursive version of the binary search.

4
00:00:09,680 --> 00:00:13,760
So let me just comment this out and let's go ahead and write the function over here.

5
00:00:13,760 --> 00:00:18,050
So let's call our function binary search recursive.

6
00:00:22,210 --> 00:00:27,970
Right now this function is going to take in again the array of integers which is numb's and the target

7
00:00:27,970 --> 00:00:28,600
value.

8
00:00:28,900 --> 00:00:33,250
Now once we are inside the function, we will be recursively calling the helper function.

9
00:00:33,250 --> 00:00:33,490
All right.

10
00:00:33,490 --> 00:00:35,500
So let's go ahead and write this function.

11
00:00:35,500 --> 00:00:37,210
So const helper.

12
00:00:37,210 --> 00:00:44,350
And this function is going to take in the array which is numb's and the target value and also the left

13
00:00:44,350 --> 00:00:46,630
pointer and the right pointer.

14
00:00:46,630 --> 00:00:47,800
All right now.

15
00:00:48,620 --> 00:00:49,220
Again.

16
00:00:49,220 --> 00:00:53,930
After we have completed writing this function, all we will be doing is we will call this function once.

17
00:00:53,930 --> 00:00:59,120
So over here we will say helper and we will pass the array of integers, the target value.

18
00:00:59,120 --> 00:01:02,030
And initially the left pointer is going to be zero.

19
00:01:02,030 --> 00:01:07,280
And the right pointer is going to be the length of the array minus one, which is the right most index

20
00:01:07,280 --> 00:01:08,030
of the given array.

21
00:01:08,030 --> 00:01:10,610
So numb's dot length minus one.

22
00:01:11,440 --> 00:01:11,860
All right.

23
00:01:11,860 --> 00:01:19,150
Now again this function over here is going to either return the index where the target value is equal

24
00:01:19,150 --> 00:01:23,260
to the value at that particular index in the given array, or it will return minus one.

25
00:01:23,260 --> 00:01:27,790
So this function also the binary search recursive function also has to return that right.

26
00:01:27,790 --> 00:01:32,560
So we will just say return whatever we are going to get back from this helper function.

27
00:01:32,560 --> 00:01:34,930
Now let's go ahead and complete the helper function.

28
00:01:34,930 --> 00:01:39,400
Now over here first we will check whether left is greater than right right.

29
00:01:39,400 --> 00:01:42,400
So if left is greater than right we can just return.

30
00:01:42,400 --> 00:01:45,970
So this is the base base case of the recursive call.

31
00:01:45,970 --> 00:01:46,210
Right.

32
00:01:46,210 --> 00:01:47,860
So we have returned minus one over here.

33
00:01:47,860 --> 00:01:53,590
So at any point when we keep recursively calling the helper function and finally we reach the situation

34
00:01:53,590 --> 00:01:58,870
that left is greater than right or left is no longer less than or equal to right.

35
00:01:58,870 --> 00:02:03,670
Right if less is left is not equal to less than or equal to right, we can just say left is greater

36
00:02:03,670 --> 00:02:07,330
than right, and when left is greater than right, we will just return minus one.

37
00:02:07,330 --> 00:02:08,710
So that is our base case.

38
00:02:08,710 --> 00:02:10,270
So let me just write that over here.

39
00:02:10,270 --> 00:02:11,620
So this is the base case.

40
00:02:13,600 --> 00:02:13,960
All right.

41
00:02:13,990 --> 00:02:16,870
Now, if this is not the case, then we proceed further.

42
00:02:16,870 --> 00:02:19,420
And first we are going to calculate the middle index.

43
00:02:19,420 --> 00:02:23,590
So we can say const middle is equal to math dot floor.

44
00:02:24,800 --> 00:02:26,300
Left plus right.

45
00:02:28,470 --> 00:02:29,790
Divided by two.

46
00:02:31,210 --> 00:02:36,010
And then we're just going to check whether the target is equal to numb's at middle index.

47
00:02:36,010 --> 00:02:36,850
So let's check that.

48
00:02:36,850 --> 00:02:37,750
So if.

49
00:02:38,470 --> 00:02:41,410
Target is equal to numb's at middle.

50
00:02:41,950 --> 00:02:46,210
Then we have found the target value and we can just return the index right.

51
00:02:46,210 --> 00:02:48,730
So return middle which is the index at that point.

52
00:02:48,760 --> 00:02:54,610
Now if this is not the case we have to check whether target is less than numb's at middle.

53
00:02:54,610 --> 00:03:01,450
So if target is less than numb's at middle, in that case we just need to check the left part.

54
00:03:01,450 --> 00:03:05,200
So we're going to recursively call the helper function.

55
00:03:05,620 --> 00:03:07,720
And we are going to change the right right.

56
00:03:07,720 --> 00:03:09,970
So we we want to keep the left as it is.

57
00:03:09,970 --> 00:03:14,920
But then the right is going to change to middle minus one because we are only interested towards the

58
00:03:14,920 --> 00:03:17,830
left part of the middle index in our array.

59
00:03:17,830 --> 00:03:21,280
So we are just going to say return helper.

60
00:03:21,520 --> 00:03:25,180
And now we are again passing the array the target value.

61
00:03:27,220 --> 00:03:31,660
And left does not change, but right is going to be middle minus one.

62
00:03:31,660 --> 00:03:33,850
So we're changing the right pointer.

63
00:03:33,880 --> 00:03:34,330
All right.

64
00:03:34,360 --> 00:03:40,390
Now if this is not the case that means numb's at middle is not equal to target.

65
00:03:40,390 --> 00:03:42,430
And target is not less than numb's at middle.

66
00:03:42,430 --> 00:03:45,160
So that means target is greater than num said middle.

67
00:03:45,160 --> 00:03:49,240
So if that is the case we are only interested towards the right of the middle index.

68
00:03:49,240 --> 00:03:53,560
So we're going to change the left pointer and we will make it middle plus one.

69
00:03:53,560 --> 00:03:57,040
So in this case we are going to return helper.

70
00:03:57,400 --> 00:04:00,670
And we are again passing the array numb's the target value.

71
00:04:00,670 --> 00:04:04,240
And then we are going to change the left pointer to middle plus one.

72
00:04:04,330 --> 00:04:06,160
And then the right does not change.

73
00:04:06,160 --> 00:04:07,960
So right pointer stays as it is.

74
00:04:07,960 --> 00:04:08,950
So that's it.

75
00:04:08,950 --> 00:04:10,600
So this is the end of our function.

76
00:04:10,600 --> 00:04:11,770
So what's happening over here.

77
00:04:11,770 --> 00:04:14,620
We are again we have our helper function over here.

78
00:04:14,620 --> 00:04:18,370
The helper function will either return minus one or a particular index.

79
00:04:18,370 --> 00:04:18,670
Right.

80
00:04:18,670 --> 00:04:21,280
And when we get that we are just returning that over here.

81
00:04:21,280 --> 00:04:23,380
So that is what this function returns.

82
00:04:23,380 --> 00:04:25,600
Now how does the helper function work.

83
00:04:25,600 --> 00:04:26,410
The helper function.

84
00:04:26,410 --> 00:04:30,370
Once we are inside over here it's checking whether target is equal to num said middle.

85
00:04:30,370 --> 00:04:33,430
If so we will return that particular index which is middle.

86
00:04:33,460 --> 00:04:37,900
Now if target is less than middle, we are recursively calling the helper function again.

87
00:04:37,900 --> 00:04:40,060
And at this point we are changing the right pointer.

88
00:04:40,060 --> 00:04:40,300
Right.

89
00:04:40,330 --> 00:04:41,740
Now this call over here.

90
00:04:41,740 --> 00:04:47,110
The interesting thing to note is over here is this call over here will either return minus one or a

91
00:04:47,110 --> 00:04:47,890
particular index.

92
00:04:47,890 --> 00:04:48,190
Right.

93
00:04:48,190 --> 00:04:52,780
So if it is returning minus one again this whole function will return minus one.

94
00:04:52,780 --> 00:04:53,920
And it will come over here.

95
00:04:53,920 --> 00:04:56,290
And we are returning that minus one from this function.

96
00:04:56,290 --> 00:04:57,370
So that's how this works.

97
00:04:57,370 --> 00:05:00,010
Now let's take an example and let's walk through the code.

98
00:05:00,790 --> 00:05:03,430
So again let's try first let's test our code.

99
00:05:03,430 --> 00:05:06,160
So we have binary search recursive.

100
00:05:06,160 --> 00:05:09,910
And let's say the array is again 1234 and five.

101
00:05:09,910 --> 00:05:11,980
And let's say we are searching for the value ten.

102
00:05:11,980 --> 00:05:14,710
So let's run our code and see what's happening.

103
00:05:15,530 --> 00:05:19,250
So we are getting minus one, which is correct because minus one is not there in this array.

104
00:05:19,280 --> 00:05:21,380
Now what if we change this to five?

105
00:05:23,090 --> 00:05:24,920
So we get index four, which is correct.

106
00:05:24,950 --> 00:05:27,140
Now what if we change this to one.

107
00:05:28,590 --> 00:05:30,870
So we get index zero, which is also correct.

108
00:05:30,900 --> 00:05:32,250
Now let's try to.

109
00:05:34,290 --> 00:05:37,140
So we get index one which is this index over here.

110
00:05:37,140 --> 00:05:38,760
So yes our function is working.

111
00:05:38,760 --> 00:05:40,230
Now let's take an example.

112
00:05:40,230 --> 00:05:42,720
And let's just walk through the code and see what's happening.

113
00:05:42,720 --> 00:05:43,260
All right.

114
00:05:43,260 --> 00:05:45,150
So we have this call over here.

115
00:05:45,150 --> 00:05:48,060
Let's try to walk through the code and see what's happening over here.

116
00:05:48,060 --> 00:05:52,170
So we pass this array over here to the binary search recursive function.

117
00:05:52,170 --> 00:05:54,390
And the target value is equal to two.

118
00:05:54,390 --> 00:05:55,560
Now we come inside.

119
00:05:55,560 --> 00:05:57,660
So this is the definition of the helper function.

120
00:05:57,660 --> 00:06:00,150
And then over here we are calling the helper function.

121
00:06:00,150 --> 00:06:02,310
And let me just track this over here.

122
00:06:02,310 --> 00:06:03,930
This is going to be our call stack.

123
00:06:03,930 --> 00:06:04,350
All right.

124
00:06:04,350 --> 00:06:07,560
So in the call stack we already have the binary search recursive.

125
00:06:07,560 --> 00:06:09,030
But I'm not writing it over here.

126
00:06:09,030 --> 00:06:10,800
We'll just track the helper function.

127
00:06:10,800 --> 00:06:12,900
So this is the first call to the helper function.

128
00:06:12,900 --> 00:06:13,320
All right.

129
00:06:13,320 --> 00:06:16,440
And at this point the left index is going to be zero.

130
00:06:16,440 --> 00:06:19,680
And the right index is going to be numb's dot length minus one.

131
00:06:19,680 --> 00:06:23,400
So the length over here is five five minus one is equal to four.

132
00:06:23,400 --> 00:06:25,170
So we are calling it with zero and four.

133
00:06:25,170 --> 00:06:28,860
So once we are inside the function we are checking whether zero is greater than four.

134
00:06:28,890 --> 00:06:29,730
That's falsy.

135
00:06:29,730 --> 00:06:31,320
So we don't go inside over here.

136
00:06:31,320 --> 00:06:35,700
And then we are going to calculate middle middle is going to be zero plus four divided by two which

137
00:06:35,700 --> 00:06:36,930
is two at this point.

138
00:06:36,930 --> 00:06:42,930
And then we are checking uh let me just write the indices over here 0123 and four.

139
00:06:42,930 --> 00:06:44,670
So middle is pointing over here.

140
00:06:44,670 --> 00:06:47,940
And we are checking this value whether it's equal to target.

141
00:06:47,940 --> 00:06:49,410
So over here we have three right.

142
00:06:49,410 --> 00:06:50,340
So this is three.

143
00:06:50,880 --> 00:06:53,130
And we can see that three is not equal to two.

144
00:06:53,160 --> 00:06:54,930
So it won't go inside over here.

145
00:06:54,930 --> 00:06:56,610
Then we come to the next line of code.

146
00:06:56,610 --> 00:06:59,670
We are checking whether target which is two is two less than three.

147
00:06:59,670 --> 00:07:00,510
That's truthy.

148
00:07:00,510 --> 00:07:04,260
So again we are going to return whatever we are going to get back from this call.

149
00:07:04,260 --> 00:07:04,560
Right.

150
00:07:04,560 --> 00:07:06,720
So we have the next helper call over here.

151
00:07:06,720 --> 00:07:08,310
So this is the recursive call.

152
00:07:08,310 --> 00:07:11,340
And at this point we are again passing the array.

153
00:07:11,340 --> 00:07:14,130
We are passing the target value left is not changed.

154
00:07:14,130 --> 00:07:15,390
So left is still zero.

155
00:07:15,390 --> 00:07:17,790
But right is going to be middle minus one.

156
00:07:17,790 --> 00:07:18,870
And middle was two right.

157
00:07:18,870 --> 00:07:20,850
So two minus one is going to be one.

158
00:07:20,850 --> 00:07:23,790
So we are calling the helper function with zero and one.

159
00:07:23,790 --> 00:07:25,950
So again we are inside the function over here.

160
00:07:26,610 --> 00:07:28,110
So let's just clean this up.

161
00:07:28,110 --> 00:07:30,570
And left is equal to zero.

162
00:07:30,570 --> 00:07:31,920
Right is equal to one.

163
00:07:31,920 --> 00:07:34,230
Now we are checking whether zero is greater than one.

164
00:07:34,230 --> 00:07:34,860
That's falsy.

165
00:07:34,860 --> 00:07:39,390
So we come inside over here and we are doing zero plus one divided by two and flooring it right.

166
00:07:39,390 --> 00:07:42,660
So zero plus one divided by two gives us 0.5.

167
00:07:42,660 --> 00:07:44,820
And when we floor it we get zero.

168
00:07:44,820 --> 00:07:47,310
So middle is going to point at index zero.

169
00:07:47,310 --> 00:07:49,500
And then we are checking whether target which is two.

170
00:07:49,530 --> 00:07:52,830
Is it equal to this value over here at index zero which is one.

171
00:07:52,830 --> 00:07:53,130
Right.

172
00:07:53,130 --> 00:07:54,360
So two is not equal to one.

173
00:07:54,360 --> 00:07:56,160
So we don't go inside this line of code.

174
00:07:56,160 --> 00:08:01,140
So we come over here and we are checking whether target which is two is two less than one.

175
00:08:01,140 --> 00:08:01,860
No that's false.

176
00:08:02,340 --> 00:08:03,720
So we don't continue with this line.

177
00:08:03,720 --> 00:08:08,250
So we come over here and you can see that we again call the helper function recursively.

178
00:08:08,250 --> 00:08:11,670
And now we are changing the left pointer to middle plus one.

179
00:08:11,670 --> 00:08:12,870
And middle was zero right.

180
00:08:12,870 --> 00:08:14,340
So middle plus one is one.

181
00:08:14,340 --> 00:08:17,100
And the right pointer does not change which is one itself.

182
00:08:17,100 --> 00:08:22,110
So the helper function is again called with the left index as one and the right index as one.

183
00:08:22,110 --> 00:08:24,420
So again we come inside the function over here.

184
00:08:25,050 --> 00:08:26,400
So let's clean this up.

185
00:08:26,400 --> 00:08:27,780
And left is equal to one.

186
00:08:27,780 --> 00:08:29,010
And right is equal to one.

187
00:08:29,010 --> 00:08:29,880
At this point.

188
00:08:29,880 --> 00:08:32,250
And we are checking whether one is greater than one.

189
00:08:32,250 --> 00:08:33,030
So that's falsy.

190
00:08:33,030 --> 00:08:34,650
So we don't return minus one.

191
00:08:34,650 --> 00:08:39,060
So we come over here and again we calculate middle which is one plus one divided by two.

192
00:08:39,090 --> 00:08:41,340
So at this point it's going to be one itself right.

193
00:08:41,340 --> 00:08:43,470
One plus one by two gives us one itself.

194
00:08:43,470 --> 00:08:45,060
So middle is index one.

195
00:08:45,060 --> 00:08:50,850
Now we are checking whether target is equal to the array which the array which is given to us at index

196
00:08:50,850 --> 00:08:51,270
one.

197
00:08:51,270 --> 00:08:51,480
Right.

198
00:08:51,480 --> 00:08:54,990
So let me write the index over here 0123 and four.

199
00:08:54,990 --> 00:08:56,550
So at index one we have two.

200
00:08:56,550 --> 00:08:58,470
And the target value also is equal to two.

201
00:08:58,500 --> 00:08:59,730
So these two are equal.

202
00:08:59,730 --> 00:09:05,160
So when we are doing this call right with one and one we will return middle value.

203
00:09:05,160 --> 00:09:11,880
So this call over here which is with one and one will return the index one right middle over here is

204
00:09:11,880 --> 00:09:12,090
one.

205
00:09:12,090 --> 00:09:13,260
So it will return one.

206
00:09:13,260 --> 00:09:16,440
So this function also will return this back right.

207
00:09:16,440 --> 00:09:18,150
So we get one over here as well.

208
00:09:18,150 --> 00:09:21,240
And this call which was the first call which happened over here.

209
00:09:21,240 --> 00:09:24,930
This call over here is also going to return this one over here.

210
00:09:24,930 --> 00:09:30,750
That's how the function the binary search recursive function is going to return one.

211
00:09:30,750 --> 00:09:32,010
And that's our answer over here.

212
00:09:32,010 --> 00:09:33,510
So that is how this function works.

213
00:09:33,510 --> 00:09:37,470
Now let's take a quick look at the space and time complexity over here.

214
00:09:37,470 --> 00:09:40,440
So the time complexity is again O of log n.

215
00:09:40,440 --> 00:09:41,400
Why is that so.

216
00:09:41,400 --> 00:09:44,940
Because again it's the same reason why we discussed previously as well.

217
00:09:44,940 --> 00:09:50,070
So at every step we are eliminating half of the input because we are only looking at one part, either

218
00:09:50,070 --> 00:09:51,750
the left part or the right part.

219
00:09:51,750 --> 00:09:52,020
Right.

220
00:09:52,020 --> 00:09:53,280
So either it's equal.

221
00:09:53,280 --> 00:09:54,900
Otherwise we are going to change.

222
00:09:54,900 --> 00:09:58,800
If the target value is less than numb's middle, we are changing the right pointer.

223
00:09:58,800 --> 00:10:00,780
So we are only looking at the left part.

224
00:10:00,810 --> 00:10:05,460
Now if that is not the case, we are changing the left part and we are only looking at the right part.

225
00:10:05,460 --> 00:10:08,400
So we are eliminating half of the input at every step.

226
00:10:08,400 --> 00:10:11,490
So that's why the time complexity is going to be O of log n.

227
00:10:11,490 --> 00:10:17,880
Now the space complexity is going to be O of log n as well over here because this is a recursive function.

228
00:10:17,880 --> 00:10:18,180
Right.

229
00:10:18,180 --> 00:10:24,720
So in the worst case, in the worst case we are going to have log n calls on the call stack at the same

230
00:10:24,720 --> 00:10:25,110
time.

231
00:10:25,110 --> 00:10:30,450
So that's why we can say that the space complexity is going to be O of log n, where n is the number

232
00:10:30,450 --> 00:10:31,830
of elements in our given array.

233
00:10:31,830 --> 00:10:33,180
For example, we had over here.

234
00:10:33,430 --> 00:10:34,180
Five elements.

235
00:10:34,180 --> 00:10:35,260
And again remember this.

236
00:10:35,260 --> 00:10:38,710
We have we have to floor this over here we have five elements.

237
00:10:38,710 --> 00:10:43,570
So if you do log five and if you just floor this you can see that we are going to get two.

238
00:10:44,280 --> 00:10:48,720
Now over here you can see we had three recursive calls of the helper function.

239
00:10:48,720 --> 00:10:51,330
So we are just approximating it to log n right.

240
00:10:51,330 --> 00:10:53,250
We could say it's log n plus one.

241
00:10:53,250 --> 00:10:53,820
All right.

242
00:10:53,820 --> 00:10:54,930
Because we have three over here.

243
00:10:54,930 --> 00:10:56,550
But then again one is a constant.

244
00:10:56,550 --> 00:10:57,810
So we can avoid it.

245
00:10:57,810 --> 00:11:01,980
And we can say that the space complexity of this solution is O of log n.