1
00:00:00,590 --> 00:00:01,580
Welcome back.

2
00:00:01,580 --> 00:00:04,640
Let's now go ahead and implement the binary search.

3
00:00:04,640 --> 00:00:06,800
As we discussed in the previous video.

4
00:00:06,800 --> 00:00:10,160
First we'll implement the iterative version of the binary search.

5
00:00:10,160 --> 00:00:13,640
So for this let's call our function binary search.

6
00:00:14,590 --> 00:00:15,520
Iterative.

7
00:00:17,660 --> 00:00:18,110
All right.

8
00:00:18,110 --> 00:00:23,780
Now this function is going to take in the array of integers which is numb's and the target value.

9
00:00:25,310 --> 00:00:29,540
Now, once we are inside the function, let's have two pointers left and right.

10
00:00:29,540 --> 00:00:35,240
So left is going to be equal to zero, which is the left most index of the array which is given to us.

11
00:00:35,240 --> 00:00:40,820
And right is going to be the right most index which is numb's dot length minus one.

12
00:00:41,530 --> 00:00:48,160
Now we're going to have a while loop, which will go on as long as left is less than or equal to right,

13
00:00:48,700 --> 00:00:51,400
so that we can keep searching for the number which is given to us.

14
00:00:51,430 --> 00:00:53,680
Now we will need a pointer middle.

15
00:00:53,680 --> 00:00:58,300
Let me just initialize it over here so that we don't keep initializing it at every loop.

16
00:00:58,300 --> 00:00:58,720
All right.

17
00:00:58,720 --> 00:01:00,940
So inside this we are going to calculate middle.

18
00:01:00,940 --> 00:01:03,400
And middle is going to be math dot floor.

19
00:01:06,780 --> 00:01:09,300
Left plus right divided by two.

20
00:01:10,440 --> 00:01:11,820
Now we can do ceiling also.

21
00:01:11,820 --> 00:01:13,590
But over here we're just doing floor.

22
00:01:13,620 --> 00:01:20,940
Now once we find the middle index you're going to check if the number at that particular index is equal

23
00:01:20,940 --> 00:01:23,070
to the target which is given to us or not.

24
00:01:23,070 --> 00:01:24,270
So let's do that over here.

25
00:01:24,270 --> 00:01:32,190
So if target is equal to numb's at middle in that case we have found the integer which we are searching

26
00:01:32,190 --> 00:01:32,520
for.

27
00:01:32,520 --> 00:01:35,730
And we can just return that particular index which is middle.

28
00:01:36,030 --> 00:01:42,630
Now if this is not the case, we will check whether target is less than the value at the middle index.

29
00:01:42,630 --> 00:01:50,550
So if target less than numb's at middle, if this is the case, then we'll have to search only on the

30
00:01:50,550 --> 00:01:52,500
left part from the middle index.

31
00:01:52,500 --> 00:01:55,830
So we're going to move the right index to middle minus one.

32
00:01:55,830 --> 00:01:59,250
So right is going to be equal to middle minus one.

33
00:01:59,340 --> 00:02:04,710
Now if this is not the case then we will move left to middle plus one right.

34
00:02:04,710 --> 00:02:09,600
Because if this is not the case that means that target is greater than num said middle right.

35
00:02:09,600 --> 00:02:14,670
So if that is the case then we will move our left pointer to middle plus one, because we only want

36
00:02:14,670 --> 00:02:17,370
to search in the right part of the middle value.

37
00:02:17,370 --> 00:02:17,820
All right.

38
00:02:17,820 --> 00:02:21,240
So this will keep looping as long as left is less than equal to right.

39
00:02:21,240 --> 00:02:26,670
And when we are done with this when we come out of this while loop, if we have not returned anything

40
00:02:26,670 --> 00:02:33,030
so far, that means that the target value is not there in the Nums array, so we can just return minus

41
00:02:33,030 --> 00:02:33,960
one in that case.

42
00:02:34,200 --> 00:02:34,560
All right.

43
00:02:34,560 --> 00:02:36,180
So we're done with our function.

44
00:02:36,180 --> 00:02:39,390
Now let's go ahead and test our function by calling it.

45
00:02:39,390 --> 00:02:42,060
So I'm just saying binary search iterative.

46
00:02:42,060 --> 00:02:43,950
Now we will need to pass the array.

47
00:02:43,950 --> 00:02:47,370
So let's say 12345 is the array which you're passing in.

48
00:02:47,370 --> 00:02:49,980
And let's say we are searching for the value five.

49
00:02:49,980 --> 00:02:53,190
Now let's go ahead and call the function and see what's happening.

50
00:02:55,160 --> 00:02:58,190
So you can see we are getting the value for which is correct.

51
00:02:58,190 --> 00:02:58,370
Right.

52
00:02:58,370 --> 00:03:01,610
So five is at index 40123 and four.

53
00:03:01,610 --> 00:03:02,840
So this is at index four.

54
00:03:02,840 --> 00:03:03,980
So yes that's working.

55
00:03:03,980 --> 00:03:06,230
Now let's just call it for value one.

56
00:03:06,230 --> 00:03:08,540
Let's say the target value which you're searching for is one.

57
00:03:08,630 --> 00:03:11,510
So we are getting the index zero which is this index over here.

58
00:03:11,510 --> 00:03:12,890
So yes that's also working.

59
00:03:12,890 --> 00:03:16,370
Now what if we pass a value which is clearly not there in our array.

60
00:03:17,000 --> 00:03:18,230
So we're getting minus one.

61
00:03:18,230 --> 00:03:22,700
So that means that this integer over here ten is not there in the array which is given to us.

62
00:03:22,700 --> 00:03:23,180
All right.

63
00:03:23,180 --> 00:03:24,590
So this function is working.

64
00:03:24,590 --> 00:03:27,920
Now let's take an example and just let's walk through the code.

65
00:03:28,780 --> 00:03:29,140
All right.

66
00:03:29,140 --> 00:03:32,110
So let's take this same example which we have over here.

67
00:03:33,160 --> 00:03:37,180
So we have the values one, two, three, four, five and the target value is ten.

68
00:03:37,180 --> 00:03:38,920
So that's passed to the function over here.

69
00:03:38,920 --> 00:03:40,420
Binary search iterative.

70
00:03:40,450 --> 00:03:42,910
Now initially left is pointing at zero.

71
00:03:42,910 --> 00:03:45,550
So we have left pointing to index zero.

72
00:03:45,550 --> 00:03:48,760
And then we have right pointing to numb's dot length minus one.

73
00:03:48,760 --> 00:03:50,140
So over here the length is five.

74
00:03:50,140 --> 00:03:51,610
So five minus one is four.

75
00:03:51,610 --> 00:03:52,840
So this is index four.

76
00:03:52,840 --> 00:03:54,880
So right is pointing over here.

77
00:03:54,880 --> 00:03:57,010
And then we come inside the while loop.

78
00:03:57,010 --> 00:03:58,180
Now zero.

79
00:03:58,180 --> 00:03:58,900
This is zero right.

80
00:03:58,900 --> 00:04:00,160
Zero is less than four.

81
00:04:00,160 --> 00:04:01,810
So yes this is truthy.

82
00:04:01,840 --> 00:04:03,610
So we come inside the while loop.

83
00:04:03,610 --> 00:04:06,760
Now middle is calculated as zero plus four divided by two.

84
00:04:06,760 --> 00:04:07,780
And then we are floating it.

85
00:04:07,780 --> 00:04:10,180
So we get the value of middle as two.

86
00:04:10,180 --> 00:04:15,760
And then we are going to find check the compare the value of target and numb's at middle.

87
00:04:15,760 --> 00:04:17,650
So this is zero one and two.

88
00:04:17,680 --> 00:04:18,880
So this is index two right.

89
00:04:18,880 --> 00:04:21,670
So this is where middle is pointing to at this moment.

90
00:04:21,670 --> 00:04:24,070
Now we can see that the target is ten.

91
00:04:24,070 --> 00:04:25,720
So ten is not equal to three.

92
00:04:25,720 --> 00:04:27,940
So we don't go inside over here.

93
00:04:27,940 --> 00:04:32,080
Then we come to this line of the code and we are checking whether ten is less than three.

94
00:04:32,080 --> 00:04:33,190
No that's not the case.

95
00:04:33,190 --> 00:04:33,520
Right.

96
00:04:33,520 --> 00:04:37,420
So we come over here and we move left to middle plus one.

97
00:04:37,420 --> 00:04:39,040
So let me just change the color.

98
00:04:39,040 --> 00:04:42,850
So we move left this one to middle plus one which is over here right.

99
00:04:42,850 --> 00:04:43,930
So index three.

100
00:04:43,930 --> 00:04:45,760
So left is pointing to index three.

101
00:04:45,760 --> 00:04:49,120
And then again we come over here we see that three is less than four.

102
00:04:49,120 --> 00:04:51,310
So we come inside the while loop.

103
00:04:51,310 --> 00:04:56,230
And again we calculate middle as three plus four divided by two which is 3.5.

104
00:04:56,230 --> 00:04:57,640
And then we are just flooring it.

105
00:04:57,640 --> 00:05:00,250
So we get the value of middle as three.

106
00:05:00,250 --> 00:05:03,550
So middle is also pointing to index three at this point.

107
00:05:03,580 --> 00:05:03,880
All right.

108
00:05:03,880 --> 00:05:05,590
So let me just rub these two.

109
00:05:07,580 --> 00:05:12,380
So middle is also pointing to index three and left is also pointing to index three.

110
00:05:12,410 --> 00:05:17,180
Now we are going to check the target value and compare it with the value at middle index.

111
00:05:17,180 --> 00:05:22,100
So the target value is ten and the value at the middle index is four.

112
00:05:22,100 --> 00:05:22,280
Right.

113
00:05:22,280 --> 00:05:23,690
So four is not equal to ten.

114
00:05:23,690 --> 00:05:25,250
So we don't go inside over here.

115
00:05:25,250 --> 00:05:28,460
Then we come and check whether for ten is less than four.

116
00:05:28,490 --> 00:05:29,390
That's not the case.

117
00:05:29,390 --> 00:05:30,380
So we come over here right.

118
00:05:30,380 --> 00:05:35,420
So we come again to this part and we change left and we make it middle plus one.

119
00:05:35,420 --> 00:05:35,660
Right.

120
00:05:35,660 --> 00:05:39,200
So this over here from three it's pointing to four at this moment.

121
00:05:39,200 --> 00:05:40,790
So left is also pointing at four.

122
00:05:40,790 --> 00:05:42,350
Right is also pointing at four.

123
00:05:42,350 --> 00:05:46,700
Now we come again over here we see that four less than or equal to four is truthy.

124
00:05:46,700 --> 00:05:50,360
So we come inside the while loop and we recalculate the middle value.

125
00:05:50,360 --> 00:05:51,170
At this point.

126
00:05:51,170 --> 00:05:53,810
Middle is four plus four by two which is four itself.

127
00:05:53,810 --> 00:05:55,340
So middle also is at four.

128
00:05:55,340 --> 00:05:57,560
And we are checking whether five.

129
00:05:57,590 --> 00:05:59,120
The value at index four is five.

130
00:05:59,120 --> 00:05:59,270
Right.

131
00:05:59,270 --> 00:06:00,950
We are checking whether five is equal to ten.

132
00:06:00,950 --> 00:06:02,000
That's not the case.

133
00:06:02,000 --> 00:06:03,410
So we don't go inside over here.

134
00:06:03,410 --> 00:06:04,580
Then we come over here.

135
00:06:04,580 --> 00:06:06,860
We check whether five is less than ten.

136
00:06:06,860 --> 00:06:08,780
And no whether ten is less than five.

137
00:06:08,780 --> 00:06:08,960
Right.

138
00:06:08,960 --> 00:06:10,160
Whether the target is ten.

139
00:06:10,160 --> 00:06:11,870
So is ten less than five.

140
00:06:11,870 --> 00:06:12,800
No that's not the case.

141
00:06:12,800 --> 00:06:16,490
So again we come over here and we say that left is middle plus one.

142
00:06:16,490 --> 00:06:17,960
So left becomes five.

143
00:06:17,960 --> 00:06:19,820
So right at this moment is four.

144
00:06:19,820 --> 00:06:22,130
And left is pointing to index five.

145
00:06:22,160 --> 00:06:25,520
Again we come over here and we check whether five less than or equal to four.

146
00:06:25,520 --> 00:06:26,240
That's false.

147
00:06:26,390 --> 00:06:29,330
So we come out and then we're just going to return minus one.

148
00:06:29,330 --> 00:06:31,100
So that is how the code works.

149
00:06:31,100 --> 00:06:34,550
In the case where a value is passed which is not there in our array.

150
00:06:34,550 --> 00:06:41,180
And similarly if it was there then we would have identified it over here right at some point the the

151
00:06:41,180 --> 00:06:43,700
middle pointer would be pointing to that particular value.

152
00:06:43,700 --> 00:06:46,730
Then we would have found that target is equal to numb's at middle.

153
00:06:46,730 --> 00:06:50,660
And then we would have just returned the index where the value was.

154
00:06:50,660 --> 00:06:54,500
The target value was equal to the value at that particular index of the array.

155
00:06:54,500 --> 00:06:54,860
All right.

156
00:06:54,860 --> 00:06:57,500
So this is how the iterative version of the binary search works.

157
00:06:57,500 --> 00:07:01,100
Now let's go ahead and code the recursive version of the binary search.

158
00:07:01,100 --> 00:07:03,890
And again what's the time and space complexity over here.

159
00:07:03,890 --> 00:07:05,630
Let's take a quick look at that.

160
00:07:06,590 --> 00:07:11,240
Now clearly the space complexity is equal to O of one or constant space, right?

161
00:07:11,240 --> 00:07:17,270
Because we are not using any scaling space, we are not creating a new array or a hash map, etc..

162
00:07:17,270 --> 00:07:21,560
So the space complexity over here is O of one or constant space.

163
00:07:21,560 --> 00:07:24,140
And and again you can notice that this is the iterative version.

164
00:07:24,140 --> 00:07:27,380
So that's why the space complexity is O of one we don't have.

165
00:07:27,380 --> 00:07:30,230
Again we are not using space on the recursive stack as well.

166
00:07:30,230 --> 00:07:32,120
Now what about the time complexity?

167
00:07:32,120 --> 00:07:35,810
Now the time complexity of this solution is going to be O of log n.

168
00:07:35,810 --> 00:07:36,650
Why is that so?

169
00:07:36,650 --> 00:07:40,310
Because at every step we are eliminating half of the remaining values.

170
00:07:40,310 --> 00:07:44,090
And this type of a relation is log n time complexity.

171
00:07:44,090 --> 00:07:44,420
Right.

172
00:07:44,420 --> 00:07:50,750
Again notice log of four is equal to two and log of eight is equal to three.

173
00:07:50,750 --> 00:07:55,040
So this is also another way in which you can think about it when we are doubling the size right.

174
00:07:55,040 --> 00:07:56,990
So n is the input array size.

175
00:07:56,990 --> 00:08:01,430
So when we are doubling the size the number of checks is only increasing by one.

176
00:08:01,430 --> 00:08:03,800
So that's again another way of looking at it.

177
00:08:03,800 --> 00:08:09,440
The time complexity of this solution is O of log n, and the space complexity is O of one or constant

178
00:08:09,440 --> 00:08:09,800
space.

179
00:08:09,800 --> 00:08:15,710
Because this is the iterative solution, and we are not using any extra space to come up with our solution.