1
00:00:02,180 --> 00:00:03,930
Hey, guys, what's up?

2
00:00:04,550 --> 00:00:13,040
So today we are going to learn binary search, OK, so the problem with the linear search is that it

3
00:00:13,040 --> 00:00:17,970
doesn't take into consideration whether the given is sorted or sorted.

4
00:00:18,290 --> 00:00:22,490
OK, so we will use binary search for software that is.

5
00:00:23,100 --> 00:00:29,480
So there's a condition, condition used by news such as that area must be sorted.

6
00:00:30,440 --> 00:00:34,970
OK, so binary search can only be applied if the given that is sorted.

7
00:00:35,300 --> 00:00:36,910
If that is unsorted.

8
00:00:37,430 --> 00:00:39,560
If I have unsorted.

9
00:00:39,560 --> 00:00:39,880
Eddie.

10
00:00:41,160 --> 00:00:47,970
Then binary search cannot be applied, we have to apply linear search only.

11
00:00:48,450 --> 00:00:53,520
OK, so linear search is the only option if we have unsorted every.

12
00:00:54,560 --> 00:00:59,090
But if we have sorted that, we will always use binary search.

13
00:01:00,290 --> 00:01:07,340
OK, so let's see, so we will take an example and we will try to understand how binary search works.

14
00:01:08,640 --> 00:01:14,940
So suppose my ETAs, so it must be sorted, so let's see.

15
00:01:21,860 --> 00:01:29,570
So these are indexes zero, one, two, three, four, five, six and seven, and let's say the values

16
00:01:29,570 --> 00:01:37,810
are two, four, five, eight, 20, 23, 40 and 49.

17
00:01:38,840 --> 00:01:40,070
These are the values.

18
00:01:41,230 --> 00:01:48,270
For example, I want to search for let's say I want to search for food, so how my new search works,

19
00:01:48,610 --> 00:01:50,100
it takes two pointers.

20
00:01:50,380 --> 00:01:53,740
So this is a start and this is end.

21
00:01:54,580 --> 00:01:57,380
OK, so then it will calculate.

22
00:01:57,880 --> 00:02:00,160
So Americans start plus.

23
00:02:00,160 --> 00:02:06,500
And by doing that is zero plus seven by two.

24
00:02:06,760 --> 00:02:08,690
So three point five, which is three.

25
00:02:09,190 --> 00:02:09,669
So.

26
00:02:10,699 --> 00:02:19,760
My mate is here now, there are three possibilities, so first possibility number one, if the value

27
00:02:20,000 --> 00:02:21,400
president had made.

28
00:02:22,630 --> 00:02:26,690
Is it close to the given we're lucky if this is the case.

29
00:02:27,010 --> 00:02:27,960
I will return.

30
00:02:29,050 --> 00:02:41,080
OK, so I found the key and the key is present at the next second possibility if the value added is

31
00:02:41,080 --> 00:02:42,370
greater than the key.

32
00:02:44,120 --> 00:02:52,550
So in this case, for example, it is greater than four, then I can say that my answer, that key will

33
00:02:52,550 --> 00:02:54,530
lie only in this part.

34
00:02:55,400 --> 00:03:00,180
OK, we cannot lie here, so I will discard this part.

35
00:03:00,980 --> 00:03:07,770
So what I will do and it was made minus one, so my end will come here.

36
00:03:09,050 --> 00:03:11,540
OK, and how can I discard this part?

37
00:03:11,930 --> 00:03:16,130
Because I know this is amid all these values.

38
00:03:16,130 --> 00:03:23,020
On the left hand side are smaller than mud and all the values on the right hand side are greater than

39
00:03:23,030 --> 00:03:23,290
mud.

40
00:03:23,570 --> 00:03:29,460
So these values are less than made and these values are then made because my ad is certain.

41
00:03:29,720 --> 00:03:39,950
So if the value present at Miller is greater, then that means we can only only only lie in the left

42
00:03:39,950 --> 00:03:43,520
part so I can discard the right part.

43
00:03:43,610 --> 00:03:44,040
OK.

44
00:03:44,690 --> 00:03:47,720
And similarly, if.

45
00:03:50,150 --> 00:03:55,910
Murder is a less denki then, so this is my murder.

46
00:03:56,690 --> 00:03:58,490
This is right and this is left.

47
00:03:58,880 --> 00:04:00,780
So right values are greater than murder.

48
00:04:02,360 --> 00:04:11,330
So if my murder if the that murder is less stinky, then my answer will only lie in the right part.

49
00:04:11,580 --> 00:04:13,100
In that case, I will.

50
00:04:14,400 --> 00:04:17,829
Ignore the left part and what I will do.

51
00:04:17,910 --> 00:04:25,710
Start equals method plus one, so many will come here so they start will come here.

52
00:04:26,940 --> 00:04:31,180
And my problem is not only this, I have to search only on this part.

53
00:04:32,400 --> 00:04:37,110
OK, so let's take an example and we will see what happens.

54
00:04:38,820 --> 00:04:39,360
So.

55
00:04:44,680 --> 00:04:54,370
So zero, one, two, three, four, five and six, and the values are two, five, eight.

56
00:04:55,440 --> 00:05:07,710
13, 15, 20 and 25, and I want to search for value, let's say Geike was search for five, OK, so

57
00:05:08,130 --> 00:05:09,780
first of all, this is start.

58
00:05:10,050 --> 00:05:11,070
This is my start.

59
00:05:11,370 --> 00:05:20,550
And this is my and now I will calculate made so many calls start, which is zero plus and which is six

60
00:05:20,550 --> 00:05:21,330
by two.

61
00:05:21,750 --> 00:05:25,140
So Mayday's three now this is my murder.

62
00:05:26,550 --> 00:05:30,420
So compare the value is 13 equals five.

63
00:05:30,420 --> 00:05:32,850
No logic 13.

64
00:05:32,860 --> 00:05:33,660
Guerdon five.

65
00:05:33,690 --> 00:05:35,010
Yes, the condition is true.

66
00:05:35,220 --> 00:05:37,440
My answer will lie in the left part.

67
00:05:37,650 --> 00:05:39,030
So I will discard this.

68
00:05:41,230 --> 00:05:47,710
So and it was made minus one, so that is three, minus one at two.

69
00:05:48,130 --> 00:05:49,240
So this is my end.

70
00:05:50,020 --> 00:05:51,130
This is my end.

71
00:05:52,970 --> 00:06:02,780
Now I will again calculate so murder equals start, which is zero, and which is two by two, so it

72
00:06:02,780 --> 00:06:03,830
is coming out to be one.

73
00:06:04,100 --> 00:06:05,360
So this is murder.

74
00:06:06,290 --> 00:06:07,820
This is murder.

75
00:06:08,150 --> 00:06:11,730
Now, again, I will compare is five close to five.

76
00:06:11,910 --> 00:06:12,500
Yes.

77
00:06:13,040 --> 00:06:18,050
Then what I will do, I will return mid, return mid.

78
00:06:18,350 --> 00:06:20,330
So I will return the next one.

79
00:06:21,260 --> 00:06:21,660
OK.

80
00:06:21,680 --> 00:06:23,780
So this is how by research book.

81
00:06:25,200 --> 00:06:26,820
Now, let's take one more example.

82
00:06:29,970 --> 00:06:33,150
So suppose the adays.

83
00:06:39,910 --> 00:06:48,790
Zero, one, two, three, four, five and six, and let's say the values are one, four, five, 10,

84
00:06:49,210 --> 00:06:56,770
12, 18 and 25 and I want to search for, let's say, 25, OK?

85
00:06:57,010 --> 00:06:59,080
I want to search for value 25.

86
00:07:00,880 --> 00:07:02,190
So this is my start.

87
00:07:02,890 --> 00:07:04,180
This is my end.

88
00:07:05,540 --> 00:07:14,740
First of all, calculate the milk so many medicos start plus and buy two, so many clothes, three.

89
00:07:15,410 --> 00:07:17,450
OK, so this is my mid.

90
00:07:18,860 --> 00:07:21,780
Now, compare is 10 equals 25.

91
00:07:21,800 --> 00:07:28,190
No, the second condition is stronger than 25, no, and less than 25.

92
00:07:28,340 --> 00:07:30,580
I guess the value is less than key.

93
00:07:30,890 --> 00:07:38,480
So I will search on the right hand side that is and equals three start equals murder plus one.

94
00:07:38,810 --> 00:07:40,950
So much is three plus one.

95
00:07:41,510 --> 00:07:42,570
So this is four.

96
00:07:42,670 --> 00:07:48,080
So now this is my updated start and I will discard this whole part.

97
00:07:49,310 --> 00:07:56,750
Now, what I will do, I will calculate again, so Americans, you start there's four and there's six

98
00:07:56,750 --> 00:07:59,950
by two, so is coming out to be five.

99
00:07:59,960 --> 00:08:01,370
So this is my mid.

100
00:08:03,640 --> 00:08:13,550
Now, compare is 18, close to 25, now is 18 and then 25 now is 18, less than 25.

101
00:08:13,610 --> 00:08:14,080
Yes.

102
00:08:14,650 --> 00:08:19,090
So what I will do is start equals murder plus one.

103
00:08:19,780 --> 00:08:22,450
So it is five plus one.

104
00:08:22,720 --> 00:08:24,420
So start equals six.

105
00:08:24,820 --> 00:08:26,560
So discard the left hand side.

106
00:08:29,140 --> 00:08:32,020
Now, this is my start.

107
00:08:33,340 --> 00:08:42,429
OK, now I will calculate Made against America's Start plus, and by doing so, it is coming out to

108
00:08:42,429 --> 00:08:43,450
be six.

109
00:08:43,840 --> 00:08:44,650
Now compare.

110
00:08:45,190 --> 00:08:48,100
So is AOF six.

111
00:08:48,130 --> 00:08:49,350
That is 25.

112
00:08:49,690 --> 00:08:51,040
So is 25.

113
00:08:51,040 --> 00:08:52,310
Equals 25.

114
00:08:52,380 --> 00:08:54,650
Yes, the condition is true.

115
00:08:55,000 --> 00:09:02,850
I will return MD and Maydays six, so I will return six and add the next six.

116
00:09:02,870 --> 00:09:04,630
The value 25 is present.

117
00:09:05,230 --> 00:09:07,940
OK, so this is how by new search work.

118
00:09:08,380 --> 00:09:12,520
And now let us take one more example where the key will not be found.

119
00:09:13,180 --> 00:09:15,780
OK, so this is my area.

120
00:09:23,100 --> 00:09:34,320
Zero, one, two, three, four, five, and let's say six and seven, and the values are two, three,

121
00:09:34,710 --> 00:09:46,170
four, eight, 12, 15, 20, 27, and the values that I want to search for is let's say five of five

122
00:09:46,170 --> 00:09:47,120
is not present here.

123
00:09:47,400 --> 00:09:49,100
I want to search for five.

124
00:09:50,490 --> 00:09:51,870
So this is my start.

125
00:09:52,530 --> 00:10:01,440
This is my and now let us convert the value of the murders of miracles, start bless and buy two.

126
00:10:01,920 --> 00:10:04,710
So it is coming out to be three point five, which is three.

127
00:10:04,710 --> 00:10:07,140
Integer upon integer will be in integer.

128
00:10:07,920 --> 00:10:13,410
So this is my ID now compare it equals five.

129
00:10:13,740 --> 00:10:16,230
No eight then five.

130
00:10:16,410 --> 00:10:17,040
Yes.

131
00:10:17,280 --> 00:10:23,850
So what I will do and it was made minus when that is what is the value of three.

132
00:10:24,120 --> 00:10:27,420
So three minus one so and equals two.

133
00:10:27,870 --> 00:10:30,240
So this is the new value of end.

134
00:10:31,200 --> 00:10:34,410
And what I will do, I will discard the right hand side.

135
00:10:36,360 --> 00:10:46,410
Now, again, calculate what is the value of milk, which is start plus and buy to sell to buy two is

136
00:10:46,410 --> 00:10:46,740
one.

137
00:10:47,160 --> 00:10:48,120
So this is my.

138
00:10:49,050 --> 00:10:49,980
This is made.

139
00:10:50,940 --> 00:10:52,330
Now compare the value of milk.

140
00:10:52,770 --> 00:10:54,770
So is three equals five.

141
00:10:54,990 --> 00:10:55,460
No.

142
00:10:55,980 --> 00:10:57,960
So is triggered then five.

143
00:10:58,180 --> 00:10:58,690
No.

144
00:10:59,130 --> 00:11:00,000
So it's three.

145
00:11:00,000 --> 00:11:00,880
Less than five.

146
00:11:01,130 --> 00:11:01,520
Yes.

147
00:11:01,770 --> 00:11:06,820
So what I will do is start equals murd plus one.

148
00:11:07,380 --> 00:11:08,630
So what is the value of made.

149
00:11:09,890 --> 00:11:10,800
So one plus one.

150
00:11:10,920 --> 00:11:14,940
The value of start is to so start will reach here.

151
00:11:16,590 --> 00:11:26,160
Now again calculate the value of milk which is start plus and by doing so four by two is two.

152
00:11:26,460 --> 00:11:27,630
So this is my mid.

153
00:11:28,380 --> 00:11:29,400
This is mid.

154
00:11:30,320 --> 00:11:40,650
Now, what I will do, I will compare the values, so is four equals five no is for them, five no.

155
00:11:41,060 --> 00:11:43,280
So is for less than five.

156
00:11:43,460 --> 00:11:44,000
Yes.

157
00:11:44,270 --> 00:11:48,780
So what I will do is start equals murder plus one.

158
00:11:49,370 --> 00:11:52,070
So what is the value of Modesto's or two.

159
00:11:52,070 --> 00:11:52,580
Plus one.

160
00:11:52,910 --> 00:11:56,180
So start is three, so my start will come here.

161
00:11:57,720 --> 00:11:58,950
So this is my start.

162
00:11:59,550 --> 00:12:04,380
Now, what happened is start is three and is two.

163
00:12:06,920 --> 00:12:10,410
This is a start and this is end, OK?

164
00:12:10,610 --> 00:12:15,050
So what happened here is start becomes greater than end.

165
00:12:15,560 --> 00:12:25,220
So if this is the condition, that means I can say I will stop and I will report that the key is not

166
00:12:25,880 --> 00:12:28,220
present, key not found.

167
00:12:28,670 --> 00:12:37,550
OK, so if my start becomes an end, I will stop and I will report my answer that the given key is not

168
00:12:37,550 --> 00:12:39,110
present in the Eddie.

169
00:12:41,270 --> 00:12:44,690
OK, so this is how binary search works.

170
00:12:45,840 --> 00:12:50,220
Now, let us try to find how many number of steps by new search will take.

171
00:12:51,390 --> 00:12:58,410
OK, so what I am doing, I am calculating the value of the method, which is a start plus and two,

172
00:12:59,040 --> 00:13:04,560
and then I'm comparing with key, I'm comparing these two values.

173
00:13:05,130 --> 00:13:11,310
And each time I'm comparing these values, what I'm doing, I am reducing my number of elements on which

174
00:13:11,310 --> 00:13:12,060
I have to search.

175
00:13:12,900 --> 00:13:15,900
OK, so if is Denki.

176
00:13:17,320 --> 00:13:19,190
And it was made of minus one.

177
00:13:19,480 --> 00:13:23,740
So if there were any elements, so I suppose there are any elements.

178
00:13:25,110 --> 00:13:32,820
This is made and if this is good denki what I did, I will put my pointer here.

179
00:13:33,360 --> 00:13:34,700
This is start and this is end.

180
00:13:34,980 --> 00:13:37,790
So this is my new search space.

181
00:13:39,030 --> 00:13:41,310
So this is my new search space.

182
00:13:41,870 --> 00:13:44,980
We will only be present here, otherwise we will not be there.

183
00:13:45,540 --> 00:13:53,010
So initially I was searching on any elements then I am searching on envie two elements.

184
00:13:55,290 --> 00:14:02,090
OK, and we will repeat the same process here also, I will admit I will come key and similarly, if

185
00:14:02,220 --> 00:14:07,320
it is less than what I will do, start equals murder plus one.

186
00:14:07,620 --> 00:14:10,950
So start will come here and I will discard this part.

187
00:14:11,520 --> 00:14:14,010
So again, these are and by two elements only.

188
00:14:14,940 --> 00:14:19,330
So what I am doing, I am decreasing my search space by two.

189
00:14:19,620 --> 00:14:22,200
So next time I will search on and buy four elements.

190
00:14:24,580 --> 00:14:26,930
Then end by eight elements and so on.

191
00:14:27,580 --> 00:14:34,840
OK, so each time I am reducing my search of space, the search space means the number of elements on

192
00:14:34,840 --> 00:14:36,060
which you have to search.

193
00:14:36,070 --> 00:14:37,550
You have to perform a search operation.

194
00:14:38,380 --> 00:14:39,550
So what is happening here?

195
00:14:39,880 --> 00:14:41,380
Initially, I have to search.

196
00:14:43,420 --> 00:14:51,550
And elements, then I will calculate and then compare, then I have to search in and buy two elements,

197
00:14:53,110 --> 00:14:56,010
then I have to search for and buy four elements.

198
00:14:56,020 --> 00:15:01,150
I will search in and buy four elements for the gunky and it will keep going on.

199
00:15:02,050 --> 00:15:06,620
Let's see the number of steps in binary search is key.

200
00:15:07,140 --> 00:15:16,840
OK, let's say a binary search takes steps in binary search take steps so finally end upon to the power

201
00:15:16,990 --> 00:15:17,350
key.

202
00:15:19,050 --> 00:15:28,200
OK, so when this Minnesota will stop, when there is only one element in the area so and to a close

203
00:15:28,210 --> 00:15:37,200
one, that is this Minnesota will stop only when there is only one element in the area because I cannot

204
00:15:37,320 --> 00:15:39,630
divide one element into two 1/2.

205
00:15:39,900 --> 00:15:45,780
OK, so and it goes to the patchwork taking log on both the sides.

206
00:15:46,050 --> 00:15:54,300
So log and it goes back log to and K equals log and with the base to.

207
00:15:54,720 --> 00:15:58,260
And I told you that constant doesn't matter.

208
00:15:58,650 --> 00:16:02,880
So Keiko's log of N constant doesn't matter.

209
00:16:03,270 --> 00:16:04,980
So give us the number of steps.

210
00:16:06,180 --> 00:16:14,400
And this is a log and it's a binary search, binary search takes log off and steps.

211
00:16:16,240 --> 00:16:18,570
So what is the time complexity of binary search?

212
00:16:18,930 --> 00:16:24,420
It is big off log and and linear search time.

213
00:16:24,420 --> 00:16:26,620
Complexity of linear search was off.

214
00:16:26,640 --> 00:16:30,390
And so this is for sorted Eddie.

215
00:16:33,030 --> 00:16:42,150
OK, so if the given that is sorted, then binary search is much, much more efficient than linear search.

216
00:16:42,970 --> 00:16:48,630
OK, so this is it for this video and next video, I will write the code for Binary Search.

217
00:16:49,220 --> 00:16:52,070
OK, so if you have any doubt, feel free to ask.

218
00:16:52,140 --> 00:16:52,740
Thank you.

