1
00:00:00,490 --> 00:00:01,420
Welcome back.

2
00:00:01,420 --> 00:00:05,350
In this video we are going to try to understand the binary search algorithm.

3
00:00:05,350 --> 00:00:07,600
So for this let's take a sample array.

4
00:00:07,600 --> 00:00:09,460
So we have this array over here.

5
00:00:09,460 --> 00:00:13,480
And let's say that the target for which we are searching is equal to nine.

6
00:00:13,480 --> 00:00:17,110
So let's go ahead and write the indices of these elements in the array.

7
00:00:17,110 --> 00:00:19,450
So we have the indexes from 0 to 9.

8
00:00:19,450 --> 00:00:21,610
And we are searching for the value nine.

9
00:00:21,610 --> 00:00:26,380
Now for the binary search we are going to have two pointers the left and the right pointer.

10
00:00:26,380 --> 00:00:31,450
The left pointer is going to point to the left most index, which is zero, and the right pointer is

11
00:00:31,450 --> 00:00:34,510
going to point to the right most index, which is nine.

12
00:00:34,510 --> 00:00:40,030
Now we will go ahead and calculate the middle which is the floor of left plus right divided by two.

13
00:00:40,030 --> 00:00:42,040
Now we could have done floor or ceiling.

14
00:00:42,040 --> 00:00:42,940
It does not matter.

15
00:00:42,940 --> 00:00:44,740
But we cannot take a decimal value.

16
00:00:44,740 --> 00:00:47,980
That's why we have to either take the floor value or the ceiling value.

17
00:00:47,980 --> 00:00:50,020
So over here let's go with the floor value.

18
00:00:50,020 --> 00:00:54,190
Now zero plus nine divided by two is equal to 4.5.

19
00:00:54,190 --> 00:00:56,260
And when we floor this we will get four.

20
00:00:56,260 --> 00:00:58,840
So middle is going to point at index four.

21
00:00:58,840 --> 00:01:00,340
At this point all right.

22
00:01:00,370 --> 00:01:06,400
Now we are going to check whether the value at the middle index which is 11 is that value equal to nine.

23
00:01:06,400 --> 00:01:10,510
So we see that array at middle over here which is 11 is not equal to nine.

24
00:01:10,510 --> 00:01:10,810
All right.

25
00:01:10,810 --> 00:01:11,680
So we proceed.

26
00:01:11,680 --> 00:01:15,700
Now we go ahead and check whether the target value is it less than this value.

27
00:01:15,700 --> 00:01:17,350
Or is it greater than this value.

28
00:01:17,350 --> 00:01:22,030
Now over here we see that the target is less than the value over here.

29
00:01:22,030 --> 00:01:22,210
Right.

30
00:01:22,210 --> 00:01:23,770
So nine is less than 11.

31
00:01:23,770 --> 00:01:29,800
So that means that the value, the target value if it is there in the array which is given to us, has

32
00:01:29,800 --> 00:01:31,450
to be only on the left part.

33
00:01:31,450 --> 00:01:31,780
Right.

34
00:01:31,780 --> 00:01:33,340
It cannot be on the right part.

35
00:01:33,340 --> 00:01:35,380
So this is the left part from the middle index.

36
00:01:35,380 --> 00:01:36,790
And this is the right part.

37
00:01:36,790 --> 00:01:37,120
All right.

38
00:01:37,120 --> 00:01:38,050
So this is the middle.

39
00:01:38,050 --> 00:01:41,980
Now because the target value is less than whatever we have over here.

40
00:01:41,980 --> 00:01:43,720
It cannot be in the right part.

41
00:01:43,720 --> 00:01:47,110
Right part because the array which is given to us is sorted.

42
00:01:47,110 --> 00:01:47,470
Right.

43
00:01:47,470 --> 00:01:51,220
So whatever is to the right of middle has to be greater than middle.

44
00:01:51,220 --> 00:01:53,530
And we see that target is less than middle.

45
00:01:53,530 --> 00:01:54,580
The value at middle right.

46
00:01:54,580 --> 00:01:57,190
So we can straightforward eliminate this part.

47
00:01:57,190 --> 00:02:01,450
And we are only concerned with the left part with respect to the middle index.

48
00:02:01,450 --> 00:02:01,810
All right.

49
00:02:01,810 --> 00:02:06,220
So for this we are going to move the right pointer from here.

50
00:02:06,220 --> 00:02:08,860
We are going to move it to middle minus one.

51
00:02:08,860 --> 00:02:11,320
Because we are only concerned with this part at this point.

52
00:02:11,320 --> 00:02:11,650
Right.

53
00:02:11,650 --> 00:02:18,220
So now left is pointing at index zero and right is pointing at middle minus one which is index three.

54
00:02:18,220 --> 00:02:18,730
All right.

55
00:02:18,730 --> 00:02:23,080
So now we are going to calculate again the new middle where left is this.

56
00:02:23,080 --> 00:02:23,980
And right is this.

57
00:02:23,980 --> 00:02:26,680
So you can see that the previous middle was over here.

58
00:02:26,680 --> 00:02:32,320
And because the target was less than the value over here we have eliminated half of the input.

59
00:02:32,320 --> 00:02:32,800
Right.

60
00:02:32,800 --> 00:02:35,050
So this is the beauty of the binary search.

61
00:02:35,050 --> 00:02:39,400
At every step we will eliminate half or almost half of the data which we have.

62
00:02:39,400 --> 00:02:39,790
All right.

63
00:02:39,790 --> 00:02:42,520
So over here we have 12345.

64
00:02:42,520 --> 00:02:43,840
So these five values.

65
00:02:43,840 --> 00:02:45,940
And then over here we have 1234.

66
00:02:45,940 --> 00:02:46,270
Right.

67
00:02:46,270 --> 00:02:47,680
And again 11 was the middle.

68
00:02:47,680 --> 00:02:51,130
So we have eliminated this which is almost half of the remaining right.

69
00:02:51,130 --> 00:02:54,370
So we already did a check whether target was equal to this value.

70
00:02:54,370 --> 00:02:55,600
And we found it is not.

71
00:02:55,600 --> 00:02:58,480
And then only nine values over here we have four.

72
00:02:58,480 --> 00:02:59,950
And over here we have five right.

73
00:02:59,950 --> 00:03:02,320
So total of nine values were remaining.

74
00:03:02,320 --> 00:03:07,360
Now because target is less than the middle value we have eliminated these five values right.

75
00:03:07,360 --> 00:03:09,460
So again this was already eliminated.

76
00:03:09,460 --> 00:03:14,980
Plus another five values have been eliminated by moving the right pointer to middle minus one.

77
00:03:14,980 --> 00:03:16,660
So this is the beauty of the binary search.

78
00:03:16,660 --> 00:03:17,650
So let's proceed.

79
00:03:17,650 --> 00:03:19,360
So left is now pointing to zero.

80
00:03:19,360 --> 00:03:20,920
And right is pointing to three.

81
00:03:20,920 --> 00:03:26,590
Again we calculate middle which is floor of left plus right divided by two which is equal to zero plus

82
00:03:26,590 --> 00:03:27,640
three divided by two.

83
00:03:27,670 --> 00:03:29,290
So you get 1.5.

84
00:03:29,290 --> 00:03:32,320
And when we floor 1.5 we get one.

85
00:03:32,320 --> 00:03:35,020
So middle is going to point at index one.

86
00:03:35,650 --> 00:03:37,990
Now we again proceed with the same manner.

87
00:03:37,990 --> 00:03:42,730
We are going to check whether target is equal to the value at index middle.

88
00:03:42,730 --> 00:03:43,090
All right.

89
00:03:43,090 --> 00:03:44,650
So the value over here is three.

90
00:03:44,650 --> 00:03:47,200
So is nine equal to right middle.

91
00:03:47,200 --> 00:03:52,540
Again we see that it's not equal right now at this point we are going to check whether the target value

92
00:03:52,540 --> 00:03:54,940
is it greater than middle or less than middle.

93
00:03:54,940 --> 00:03:57,580
Over here we see that nine is greater than three.

94
00:03:57,580 --> 00:04:00,190
So nine is greater than array at middle.

95
00:04:00,190 --> 00:04:01,480
So because of this.

96
00:04:01,480 --> 00:04:02,950
So again this is the middle value.

97
00:04:02,950 --> 00:04:06,280
This is the left part with respect to the middle value.

98
00:04:06,280 --> 00:04:07,810
And this is the right part right.

99
00:04:07,810 --> 00:04:10,450
So the remaining values have already been eliminated.

100
00:04:10,450 --> 00:04:11,920
So we are only having these two.

101
00:04:11,950 --> 00:04:13,960
So we already made a check with this value.

102
00:04:13,960 --> 00:04:15,040
And we see it's not.

103
00:04:15,040 --> 00:04:16,420
So this is also eliminated.

104
00:04:16,420 --> 00:04:19,540
Now we need to decide whether we need to move left or right.

105
00:04:19,540 --> 00:04:22,150
So we see that nine is greater than right middle.

106
00:04:22,150 --> 00:04:27,310
So we know that everything to the left of middle has to be less than this value over here, because

107
00:04:27,310 --> 00:04:29,290
the array which is given to us is sorted.

108
00:04:29,290 --> 00:04:29,560
Right.

109
00:04:29,560 --> 00:04:31,900
So we are no longer concerned with the left part.

110
00:04:31,900 --> 00:04:34,570
So we are only going to check the right part.

111
00:04:34,570 --> 00:04:35,290
For this.

112
00:04:35,320 --> 00:04:38,680
We are going to move the left pointer to middle plus one.

113
00:04:38,680 --> 00:04:39,760
So let's do that.

114
00:04:39,760 --> 00:04:42,190
So we move left to middle plus one.

115
00:04:42,190 --> 00:04:43,540
Middle was pointing at one.

116
00:04:43,540 --> 00:04:45,400
So left is going to point at two.

117
00:04:45,400 --> 00:04:46,690
And we are not changing right.

118
00:04:46,690 --> 00:04:48,010
So right is pointing at three.

119
00:04:48,010 --> 00:04:48,400
All right.

120
00:04:48,400 --> 00:04:51,520
So now we are again going to calculate the middle value.

121
00:04:51,520 --> 00:04:54,640
And again you can see that we eliminated the half right.

122
00:04:54,640 --> 00:04:57,220
Almost half of the data is eliminated at every step.

123
00:04:57,220 --> 00:04:59,950
Now the left pointer is pointing at index two.

124
00:05:00,140 --> 00:05:02,420
And the right pointer is pointing at index three.

125
00:05:02,450 --> 00:05:06,800
Again we calculate middle which is floor of left plus right divided by two.

126
00:05:06,830 --> 00:05:09,440
So two plus three by two gives us 2.5.

127
00:05:09,440 --> 00:05:11,210
And when we floor it we get two.

128
00:05:11,240 --> 00:05:11,570
All right.

129
00:05:11,570 --> 00:05:14,030
So middle is going to point at index two.

130
00:05:14,620 --> 00:05:20,170
And we are going to again check and compare the target value with the value at middle index, which

131
00:05:20,170 --> 00:05:20,950
is seven.

132
00:05:20,950 --> 00:05:21,220
Right.

133
00:05:21,220 --> 00:05:22,750
So are these two equal?

134
00:05:22,750 --> 00:05:23,050
No.

135
00:05:23,050 --> 00:05:25,720
We see that nine is not equal to right middle.

136
00:05:25,720 --> 00:05:29,530
And we see that nine is actually greater than array at middle right.

137
00:05:29,530 --> 00:05:30,970
So again what do we do.

138
00:05:30,970 --> 00:05:33,190
We are only concerned to the right part.

139
00:05:33,190 --> 00:05:35,470
So again we did not have anything to the left.

140
00:05:35,470 --> 00:05:36,640
So the left is empty.

141
00:05:36,670 --> 00:05:40,330
Now at this point we see that nine is greater than array at middle.

142
00:05:40,330 --> 00:05:44,140
So we move right now if we had to move left we would have stopped right?

143
00:05:44,140 --> 00:05:48,670
Because if, for example, we were searching for something over here, let's say six, right.

144
00:05:48,670 --> 00:05:49,690
For example six.

145
00:05:49,690 --> 00:05:52,690
In that case if target was six then we would have moved left, right.

146
00:05:52,690 --> 00:05:57,640
So if we move left, then right would have been over here and left would have been over here.

147
00:05:57,640 --> 00:06:01,120
So left is no longer less than or equal to right in that case.

148
00:06:01,120 --> 00:06:02,170
And we would have stopped.

149
00:06:02,170 --> 00:06:03,640
So that is the condition right.

150
00:06:03,640 --> 00:06:04,690
So we will loop.

151
00:06:04,690 --> 00:06:05,890
We will continue.

152
00:06:06,070 --> 00:06:08,530
Either we are doing it iteratively or recursively.

153
00:06:08,530 --> 00:06:13,930
So if we do it iteratively we will continue looping as long as left is less than equal to right.

154
00:06:13,930 --> 00:06:14,320
All right.

155
00:06:14,320 --> 00:06:15,430
Now let's proceed.

156
00:06:15,430 --> 00:06:19,150
Now over here we see that nine is actually greater than the value at middle.

157
00:06:19,150 --> 00:06:23,680
So we are concerned with the right part with respect to the middle index which is only this.

158
00:06:23,680 --> 00:06:23,890
Right.

159
00:06:23,890 --> 00:06:25,660
So we just have one more value left.

160
00:06:25,660 --> 00:06:26,710
So what do we do.

161
00:06:26,710 --> 00:06:28,090
We move left to middle.

162
00:06:28,090 --> 00:06:30,190
Plus one middle was over here two.

163
00:06:30,220 --> 00:06:33,370
So left becomes two plus one which is equal to three.

164
00:06:33,370 --> 00:06:35,020
Now you can see left and right.

165
00:06:35,020 --> 00:06:36,790
Both are pointing to index three.

166
00:06:36,820 --> 00:06:38,620
Now again we continue.

167
00:06:38,620 --> 00:06:40,570
We repeat the process we are going to.

168
00:06:40,570 --> 00:06:41,650
And we have eliminated this.

169
00:06:41,650 --> 00:06:41,830
Right.

170
00:06:41,830 --> 00:06:46,840
Because we checked and we have seen that this is not equal to the value which is the target.

171
00:06:46,840 --> 00:06:50,950
So you can see again we are eliminating half of the half of the input at every step.

172
00:06:51,340 --> 00:06:52,330
Now let's proceed.

173
00:06:52,330 --> 00:06:53,950
Left is three, right is three.

174
00:06:53,950 --> 00:06:58,060
So middle is going to be three plus three divided by two which is equal to three.

175
00:06:58,060 --> 00:07:00,910
So middle is also going to point at three.

176
00:07:00,910 --> 00:07:06,070
And then over here we see that the middle value middle is at index three.

177
00:07:06,070 --> 00:07:08,860
So the value at index three is nine and the target is also nine.

178
00:07:08,860 --> 00:07:10,180
So these two are equal right.

179
00:07:10,180 --> 00:07:13,600
So because they are equal we will return this index which is middle.

180
00:07:13,600 --> 00:07:15,220
So we can just return middle.

181
00:07:15,220 --> 00:07:16,870
And that's the end of our answer.

182
00:07:16,870 --> 00:07:17,110
All right.

183
00:07:17,110 --> 00:07:18,910
So this is how the solution works.

184
00:07:18,910 --> 00:07:24,220
So you can see that at every point all we are doing is we are calculating the middle index.

185
00:07:24,220 --> 00:07:28,300
And then we are going to check whether the target is equal to the middle.

186
00:07:28,300 --> 00:07:28,690
All right.

187
00:07:28,690 --> 00:07:30,370
The value at the index middle.

188
00:07:30,370 --> 00:07:34,030
Now if it is equal then we return the middle index.

189
00:07:34,030 --> 00:07:38,620
Now if it is not equal we are going to check is target less than the middle index.

190
00:07:38,620 --> 00:07:42,730
If target is less than middle the value at middle index what do we do.

191
00:07:42,730 --> 00:07:45,550
We move right to this part which is middle minus one.

192
00:07:45,550 --> 00:07:47,590
And left does not change right now.

193
00:07:47,590 --> 00:07:52,660
If that is not the case, if target is over here, that is, if target is greater than the middle index,

194
00:07:52,660 --> 00:07:54,100
what do we do then?

195
00:07:54,100 --> 00:07:55,990
Right is already in the beginning over here right.

196
00:07:55,990 --> 00:07:59,110
So we are just going to move the left from here to here.

197
00:07:59,500 --> 00:08:01,120
And then we can keep continuing.

198
00:08:01,120 --> 00:08:03,820
That is how this function works.

199
00:08:03,820 --> 00:08:07,180
Now we can implement this iteratively or recursively.

200
00:08:07,180 --> 00:08:10,480
And we will see in the following videos how to do it in both the ways.

201
00:08:10,480 --> 00:08:10,900
All right.

202
00:08:10,900 --> 00:08:15,610
So if we are doing it recursively we are just going to have a helper function.

203
00:08:15,610 --> 00:08:19,690
And at every step we are going to pass in the left and the right indices.

204
00:08:19,690 --> 00:08:25,240
So that will depend on what part we are interested in and if not, if we are doing it iteratively,

205
00:08:25,240 --> 00:08:30,700
we will again, we will just modify the left and right, and we will keep looping as long as left is

206
00:08:30,700 --> 00:08:32,080
less than equal to right right.

207
00:08:32,080 --> 00:08:36,850
For example, if left is, uh, greater than right, for example, we are searching for something.

208
00:08:36,850 --> 00:08:41,680
Let's say we are searching for zero and the array is one, two, three and four.

209
00:08:41,680 --> 00:08:44,980
At some point, the left and right is going to point to this index.

210
00:08:44,980 --> 00:08:49,000
And we see that it's still not equal to the target value which is zero.

211
00:08:49,000 --> 00:08:51,820
And then we will move left right because the value is less.

212
00:08:51,820 --> 00:08:53,950
So we will move right to this part.

213
00:08:53,950 --> 00:08:57,340
And at that point you can see right will be less than left.

214
00:08:57,340 --> 00:09:02,290
And we can be sure that the value which for which we are searching is not there in the array which is

215
00:09:02,290 --> 00:09:03,010
given to us.

216
00:09:03,010 --> 00:09:03,490
All right.

217
00:09:03,490 --> 00:09:07,120
So let's proceed and take a look at the complexity analysis of this solution.

218
00:09:07,120 --> 00:09:12,550
Now the time complexity of this solution is going to be o of log n.

219
00:09:12,550 --> 00:09:13,360
Why is that.

220
00:09:13,360 --> 00:09:17,440
So again you can see the time complexity over here is O of log n.

221
00:09:17,440 --> 00:09:22,780
Because at every step we are eliminating roughly half of the remaining elements.

222
00:09:22,780 --> 00:09:25,570
Now this relationship over here is log n right.

223
00:09:25,570 --> 00:09:28,810
So that's why the time complexity over here is log n.

224
00:09:28,810 --> 00:09:31,030
Now you can also think of it in this manner.

225
00:09:31,030 --> 00:09:38,050
If you double n then you just have to do one extra check to either find the value for which you're searching,

226
00:09:38,050 --> 00:09:42,940
or to be sure that the value for which you're searching is not there in the array which is given to

227
00:09:42,940 --> 00:09:43,240
you.

228
00:09:43,240 --> 00:09:45,550
So let's take an example and try to understand this.

229
00:09:45,550 --> 00:09:49,840
Let's say the array which is given to us is this 2021, 22 and 23.

230
00:09:49,840 --> 00:09:52,030
And let's say the target value is ten right.

231
00:09:52,030 --> 00:09:53,920
So let's write the indices over here.

232
00:09:53,920 --> 00:09:56,230
Initially left is going to be equal to zero.

233
00:09:56,230 --> 00:09:58,090
And right is going to be equal to three.

234
00:09:58,090 --> 00:10:02,080
So middle is floor of left plus right divided by two right.

235
00:10:02,080 --> 00:10:03,910
So middle is going to be one.

236
00:10:03,910 --> 00:10:06,400
So we will see that they are not equal.

237
00:10:06,400 --> 00:10:09,250
And we will see that target is less than this value.

238
00:10:09,250 --> 00:10:11,080
So we are concerned with the left part right.

239
00:10:11,080 --> 00:10:13,660
So we are going to move right to middle minus one.

240
00:10:13,660 --> 00:10:14,170
So left and.

241
00:10:14,310 --> 00:10:19,440
Right is going to point to zero, and then middle is going to be zero plus zero divided by two which

242
00:10:19,440 --> 00:10:20,010
is zero.

243
00:10:20,010 --> 00:10:21,210
So we get 20.

244
00:10:21,210 --> 00:10:23,220
So we're going to check whether ten is equal to 20.

245
00:10:23,220 --> 00:10:24,960
We see it's not equal.

246
00:10:24,960 --> 00:10:27,930
And then we see that ten is less than 20.

247
00:10:27,930 --> 00:10:29,040
So we will move right.

248
00:10:29,040 --> 00:10:29,250
Right.

249
00:10:29,250 --> 00:10:30,570
So we will move the right index.

250
00:10:30,570 --> 00:10:34,140
So right will come over here and left will still point over here.

251
00:10:34,140 --> 00:10:37,710
And then we see that left is no longer less than or equal to right.

252
00:10:37,710 --> 00:10:41,610
And we can be sure that this value is not there in the array which is given to us.

253
00:10:41,610 --> 00:10:43,770
So you can see that we made two checks, right.

254
00:10:43,770 --> 00:10:49,380
We made a check over here when when left was at pointing to zero and right was pointing to three.

255
00:10:49,380 --> 00:10:53,220
And then we made a check over here where left and right were pointing to zero.

256
00:10:53,220 --> 00:10:54,210
So two checks right.

257
00:10:54,210 --> 00:10:55,800
So we did two checks in this case.

258
00:10:55,800 --> 00:10:58,950
Now let's double the size of the array to eight.

259
00:11:00,000 --> 00:11:03,810
And let's say we are still searching for the value target ten.

260
00:11:03,810 --> 00:11:04,200
All right.

261
00:11:04,200 --> 00:11:05,910
So let's write the indices over here.

262
00:11:05,910 --> 00:11:07,170
Now over here.

263
00:11:07,170 --> 00:11:08,700
How many checks would we do right.

264
00:11:08,700 --> 00:11:12,750
Initially the left and right pointers are at zero and seven.

265
00:11:12,750 --> 00:11:14,250
So the middle would be at three.

266
00:11:14,250 --> 00:11:15,720
So we do one check over here.

267
00:11:15,720 --> 00:11:18,000
We see that it's not equal.

268
00:11:18,000 --> 00:11:20,610
And we see that the target is less than this value over here.

269
00:11:20,610 --> 00:11:22,650
So this much is eliminated right.

270
00:11:22,650 --> 00:11:24,720
So left is still over here.

271
00:11:24,720 --> 00:11:26,310
And right is going to be over here.

272
00:11:26,310 --> 00:11:26,580
Right.

273
00:11:26,580 --> 00:11:29,280
So left is at zero and right is going to be at two.

274
00:11:29,310 --> 00:11:32,130
So zero plus two divided by two gives us one right.

275
00:11:32,130 --> 00:11:33,810
So middle is going to be at one.

276
00:11:33,810 --> 00:11:35,400
So we make this check over here.

277
00:11:35,400 --> 00:11:36,840
And we see they are not equal.

278
00:11:36,840 --> 00:11:38,010
So that's the second check.

279
00:11:38,010 --> 00:11:39,810
So we see they are not equal.

280
00:11:40,260 --> 00:11:42,660
And we see that ten is less than 21.

281
00:11:42,660 --> 00:11:44,310
So we eliminate the right part.

282
00:11:44,310 --> 00:11:44,580
Right.

283
00:11:44,580 --> 00:11:46,230
So again right is moved over here.

284
00:11:46,230 --> 00:11:49,110
So left and right will now point to index zero.

285
00:11:49,110 --> 00:11:51,900
And the middle also is going to be at index zero.

286
00:11:51,900 --> 00:11:53,910
So we are checking whether ten is equal to 20.

287
00:11:53,910 --> 00:11:55,080
Again they are not equal.

288
00:11:55,080 --> 00:11:57,150
So we move right to the left.

289
00:11:57,150 --> 00:12:00,330
And at this point left is no longer less than or equal to right.

290
00:12:00,330 --> 00:12:01,170
And we break out.

291
00:12:01,170 --> 00:12:03,570
So again you can see we did three checks over here.

292
00:12:03,570 --> 00:12:03,810
Right.

293
00:12:03,810 --> 00:12:06,690
So for index zero one and zero.

294
00:12:06,690 --> 00:12:10,080
So we did three checks when the size of the input was doubled.

295
00:12:10,080 --> 00:12:12,630
So over here we had four elements and we do two checks.

296
00:12:12,630 --> 00:12:15,360
Over here we have eight elements and we do three checks.

297
00:12:15,360 --> 00:12:18,540
So this type of a relationship is also log n.

298
00:12:18,540 --> 00:12:18,720
Right.

299
00:12:18,720 --> 00:12:25,230
Because we know that log four is equal to two and log eight where from four we are doubling to eight

300
00:12:25,230 --> 00:12:26,340
is equal to three.

301
00:12:26,340 --> 00:12:28,380
That is we are only increasing by one.

302
00:12:28,380 --> 00:12:30,390
So two plus one is equal to three.

303
00:12:30,390 --> 00:12:34,890
So that's why the time complexity of this solution is equal to o of log n.

304
00:12:34,890 --> 00:12:36,990
Now what about the space complexity.

305
00:12:36,990 --> 00:12:42,030
Now the space complexity of this solution will depend on how we implement the binary search.

306
00:12:42,030 --> 00:12:46,020
Now we can implement the binary search iteratively or recursively.

307
00:12:46,020 --> 00:12:50,370
And in the subsequent videos we will see both ways of writing the binary search.

308
00:12:50,370 --> 00:12:55,950
Now if we do it iteratively, the space complexity is going to be O of one or constant space.

309
00:12:55,950 --> 00:13:01,050
Because we are not using any auxiliary space, we are not using, we are not creating a new array or

310
00:13:01,050 --> 00:13:02,160
a hash map, etc..

311
00:13:02,160 --> 00:13:07,050
So the space complexity is going to be constant space if we implement it iteratively.

312
00:13:07,050 --> 00:13:12,330
Now, if we implement the same solution, the binary search recursively, then the space complexity

313
00:13:12,330 --> 00:13:14,190
is going to be O of log n.

314
00:13:14,190 --> 00:13:15,600
So let's try to understand why.

315
00:13:15,600 --> 00:13:17,580
So over here we have this sample array.

316
00:13:18,210 --> 00:13:20,460
And let's say the target we are searching for is nine.

317
00:13:20,460 --> 00:13:24,390
So initially the left pointer and right pointer is going to be at zero and nine.

318
00:13:24,390 --> 00:13:24,720
Right.

319
00:13:24,720 --> 00:13:27,030
And we find the middle at four.

320
00:13:27,030 --> 00:13:28,830
So this is in the first call right.

321
00:13:28,830 --> 00:13:30,750
So in the first call it's going to be like this.

322
00:13:30,750 --> 00:13:36,180
Now in the next call we are going to move the right pointer to middle minus one which is over here.

323
00:13:36,180 --> 00:13:37,800
So left is going to be at zero.

324
00:13:37,800 --> 00:13:39,810
And right is going to be at three right.

325
00:13:39,810 --> 00:13:45,840
So in this manner we are going to call the helper function recursively with changing the left and right

326
00:13:45,840 --> 00:13:46,680
pointers.

327
00:13:46,680 --> 00:13:47,160
All right.

328
00:13:47,160 --> 00:13:51,660
So the same function is going to be called with these two pointers at the second instance.

329
00:13:51,660 --> 00:13:58,500
So the total number of instances at the same time in the call stack is going to be of the order of log

330
00:13:58,500 --> 00:13:58,650
n.

331
00:13:58,650 --> 00:14:01,890
So that's why we can say that the space complexity is log n.

332
00:14:01,890 --> 00:14:05,430
So for example over here we have a total of ten elements.

333
00:14:05,430 --> 00:14:07,920
So log ten when we flow this right.

334
00:14:07,920 --> 00:14:08,730
Log ten.

335
00:14:08,730 --> 00:14:12,810
When we flow this is going to be equal to three because log eight is three.

336
00:14:12,810 --> 00:14:15,540
And then log 16 is going to be equal to four.

337
00:14:15,540 --> 00:14:15,870
Right.

338
00:14:15,870 --> 00:14:19,350
So log eight two log 15.

339
00:14:19,350 --> 00:14:21,960
When we flow it is going to be equal to three.

340
00:14:21,960 --> 00:14:26,250
Now let's try to understand over here we we've seen that there is going to be one call.

341
00:14:26,340 --> 00:14:28,110
Let me just write the call stack over here.

342
00:14:28,110 --> 00:14:32,160
There is a call where left is zero and right is nine.

343
00:14:32,160 --> 00:14:32,430
All right.

344
00:14:32,430 --> 00:14:33,750
And we are searching for nine.

345
00:14:34,110 --> 00:14:38,700
Now we move in right over here in the second call and left is zero.

346
00:14:39,570 --> 00:14:44,250
And right is going to be equal to three, and middle is going to be equal to over here one.

347
00:14:44,250 --> 00:14:44,490
Right.

348
00:14:44,490 --> 00:14:45,960
Again they are not going to be equal.

349
00:14:45,960 --> 00:14:50,850
So we are going to move left to index two because target is greater than this three over here.

350
00:14:50,850 --> 00:14:51,180
Right.

351
00:14:51,180 --> 00:14:52,590
So left is going to be over here.

352
00:14:52,590 --> 00:14:56,610
So the next call is going to be with two and three.

353
00:14:56,610 --> 00:14:57,870
So index is going to be two.

354
00:14:57,870 --> 00:15:01,140
Left index is two right index is going to be equal to three.

355
00:15:01,140 --> 00:15:03,330
And the middle value is going to be two.

356
00:15:03,360 --> 00:15:04,710
Again they are not equal.

357
00:15:04,710 --> 00:15:06,630
So we are going to move left over here.

358
00:15:06,630 --> 00:15:11,040
And we will make one more call where the left index is going to be equal to three.

359
00:15:11,040 --> 00:15:13,260
And right index is also equal to three.

360
00:15:13,260 --> 00:15:13,560
Right.

361
00:15:13,560 --> 00:15:19,890
And then at that point we will see that yes target is equal to the value at middle which is middle will

362
00:15:19,890 --> 00:15:20,910
be three at that point.

363
00:15:20,910 --> 00:15:22,560
And the value over here is also nine right.

364
00:15:22,560 --> 00:15:26,670
So over here you can see we have four calls on the call stack.

365
00:15:26,670 --> 00:15:31,950
So we can say that the space complexity is going to be log n plus one because that's three plus one

366
00:15:31,950 --> 00:15:32,700
which is four.

367
00:15:32,700 --> 00:15:34,140
But then one is a constant.

368
00:15:34,140 --> 00:15:35,190
So we can avoid it.

369
00:15:35,190 --> 00:15:39,360
So we can say that the space complexity is of the order of log n.

370
00:15:39,360 --> 00:15:41,460
So the time complexity is not going to change.

371
00:15:41,460 --> 00:15:43,740
It's going to be O of log n itself over here.

372
00:15:43,740 --> 00:15:49,590
Whether we do it iteratively or recursively, the time complexity is still O of log n, but then the

373
00:15:49,590 --> 00:15:54,030
space complexity will depend on how we implement the solution.

374
00:15:54,030 --> 00:15:54,450
All right.

375
00:15:54,450 --> 00:15:59,400
Now again why is that so it's because we are using the space on the call stack.