1
00:00:02,170 --> 00:00:03,950
Hey, guys, what's up?

2
00:00:04,390 --> 00:00:09,540
So in the last video, I explained to you the concept of binary search.

3
00:00:09,700 --> 00:00:13,540
Now in this video, we will see the code for binary search.

4
00:00:14,080 --> 00:00:16,379
So the code for Vinessa is very simple.

5
00:00:16,720 --> 00:00:17,460
What will I do?

6
00:00:17,650 --> 00:00:24,520
First of all, I will take two variables and start, which is initially zero and end and which is and

7
00:00:24,520 --> 00:00:25,190
minus one.

8
00:00:25,600 --> 00:00:28,150
OK, so if I remember if I have an error.

9
00:00:28,390 --> 00:00:36,130
So START was at the first start, was pointing towards the first index and this end was added last.

10
00:00:36,890 --> 00:00:40,040
OK, so how many times find the mirror and compare.

11
00:00:40,330 --> 00:00:46,040
So I told you will start is less than or close to the end.

12
00:00:46,540 --> 00:00:54,400
So in the last video we have seen an example that if my start becomes than end then I can see that the

13
00:00:54,520 --> 00:00:59,540
key card found ok, know found start and then end.

14
00:00:59,950 --> 00:01:03,610
So I am doing the same Wildstar this list and I close to end.

15
00:01:03,610 --> 00:01:05,140
What I will do I will find.

16
00:01:05,950 --> 00:01:13,260
So Medical's start plus and by two now I will get married.

17
00:01:13,270 --> 00:01:14,880
And now there are three cases.

18
00:01:15,220 --> 00:01:24,970
So case number one, if the value present at mid is equal to the value that we are searching for, then

19
00:01:24,980 --> 00:01:28,480
in that case I can return mid.

20
00:01:30,140 --> 00:01:32,060
OK, I am returning the index.

21
00:01:33,290 --> 00:01:41,360
Elusive, what I will do if the given value, if the value murder is greater than the value that we

22
00:01:41,360 --> 00:01:49,090
are searching for, then I can say that my value, that my key will lie on the left hand side of the

23
00:01:49,100 --> 00:01:49,440
mill.

24
00:01:49,820 --> 00:01:59,480
So this is made all the values on the left hand side are less than made and all the values on the right

25
00:01:59,480 --> 00:02:00,650
hand side are good.

26
00:02:01,580 --> 00:02:11,190
So if this value is greater than guey, which is our second case, then my key will only lie here.

27
00:02:11,600 --> 00:02:13,630
OK, so and it was made of minus one.

28
00:02:14,150 --> 00:02:19,610
Similarly, as what you can do is start equals murder plus one.

29
00:02:20,730 --> 00:02:25,640
OK, otherwise my answer will lie in the will lie in the right hand side.

30
00:02:25,950 --> 00:02:28,460
So I will start equals one plus one.

31
00:02:30,310 --> 00:02:38,450
So this is all that we have to do and when this will eliminate, OK, so when this valuable time made,

32
00:02:38,500 --> 00:02:40,880
that means start becomes good, then end.

33
00:02:41,100 --> 00:02:42,280
So this is the condition.

34
00:02:42,850 --> 00:02:45,400
So I will reach her if I reach her.

35
00:02:45,900 --> 00:02:50,430
And that means the value, the key is not present.

36
00:02:50,440 --> 00:02:52,000
So I will return minus one.

37
00:02:52,850 --> 00:03:00,170
OK, so if this Vilo terminate, if this may look damaged, naturally, what will happen.

38
00:03:01,420 --> 00:03:04,780
So when this value will terminate, this will terminate.

39
00:03:04,780 --> 00:03:06,910
When start will become guerdon.

40
00:03:06,910 --> 00:03:13,150
And and if that is the condition we have seen in the last example that the key was not there.

41
00:03:13,390 --> 00:03:15,040
So I will return minus one.

42
00:03:15,310 --> 00:03:18,100
Minus one is an invalid index.

43
00:03:18,130 --> 00:03:23,770
That is why I'm returning minus one side and returning an invalid index.

44
00:03:24,800 --> 00:03:31,250
Otherwise, if the key is found, if this is the case, if the key is found, I will likely return made

45
00:03:31,520 --> 00:03:37,670
to women, to the men and this whole program will be completed.

46
00:03:37,880 --> 00:03:38,410
OK.

47
00:03:38,450 --> 00:03:42,400
So this whole program is compared to this whole function is completed.

48
00:03:43,160 --> 00:03:44,330
So let's write the code.

49
00:03:48,500 --> 00:03:51,500
Let's say the name of the file is Binary Search.

50
00:03:53,280 --> 00:03:58,950
Called Bindi's, which called for by new such binary search.

51
00:04:00,630 --> 00:04:01,680
DARD cbb.

52
00:04:05,470 --> 00:04:09,880
OK, so this was the call for leanness, which I am copying the whole code.

53
00:04:17,730 --> 00:04:23,250
So this part will remain same, these things will be changed, so the delete.

54
00:04:24,730 --> 00:04:29,860
They knew the function will also get changed, so the name of the function is binary search.

55
00:04:33,920 --> 00:04:39,620
It will take three and put three arguments at a side of the array and lucky.

56
00:04:40,620 --> 00:04:47,250
Now, I am taking input here, I am taking the value of key, and here I will call the function

57
00:04:49,650 --> 00:04:50,340
bindery.

58
00:04:52,740 --> 00:04:53,310
Serge.

59
00:04:55,010 --> 00:05:01,850
OK, so Minnesota is taking three barometer's has been bought at a size of dairy and lucky, and it

60
00:05:01,850 --> 00:05:04,940
will return the position at which the geese present.

61
00:05:05,270 --> 00:05:09,170
If the operation equals minus one, then the key is not found.

62
00:05:09,380 --> 00:05:12,500
Else the geese found at position Bewes.

63
00:05:15,550 --> 00:05:22,480
Now, what I have to do, I have to first of all, I have to create two variables and start, which

64
00:05:22,480 --> 00:05:28,940
is initially zero and and which is initially and minus one.

65
00:05:29,510 --> 00:05:32,800
OK, so these are the two variables that I need initially.

66
00:05:35,470 --> 00:05:36,820
Now, what do I want?

67
00:05:36,850 --> 00:05:44,720
I need a loop and this loop will continue while the start is less than the close to end.

68
00:05:45,490 --> 00:05:56,660
So first of all, I will find the value of it so intimately equals start plus and by two, OK.

69
00:05:57,490 --> 00:06:06,280
Now the three cases, case number one, if the value present at mid is equal to the value that we are

70
00:06:06,280 --> 00:06:10,660
searching for, then I can return mid.

71
00:06:13,330 --> 00:06:24,010
OK, I'll see if I will check if the value presented is greater than the value that we are searching

72
00:06:24,010 --> 00:06:28,840
for, then the value can only be present on the left hand side.

73
00:06:29,260 --> 00:06:35,670
So and equals made minus one else.

74
00:06:35,830 --> 00:06:40,330
I can see that my value will be present on the right hand side.

75
00:06:40,600 --> 00:06:44,710
So start equals murd plus one.

76
00:06:45,580 --> 00:06:47,200
OK, so this is all that we have to do.

77
00:06:47,530 --> 00:06:56,260
And finally, if this value terminate you this way, terminate, that means that given key is not present.

78
00:06:56,260 --> 00:06:58,910
In that case I will return minus one.

79
00:06:59,980 --> 00:07:03,460
OK, so this is the whole court of binary search.

80
00:07:04,990 --> 00:07:05,830
Now, al-Atassi.

81
00:07:08,450 --> 00:07:10,010
OK, so Els, if.

82
00:07:16,610 --> 00:07:22,410
So the number of elements are seven and the elements are OK.

83
00:07:22,490 --> 00:07:29,540
So I'm giving unsorted input, so seven, six, five, four, three, two and one.

84
00:07:30,320 --> 00:07:32,630
And the key that we want to find is seven.

85
00:07:33,500 --> 00:07:35,770
So it is a returning key not found.

86
00:07:36,140 --> 00:07:38,070
So by the surge is not working properly.

87
00:07:38,090 --> 00:07:38,390
Why?

88
00:07:38,640 --> 00:07:44,450
Because the input that we have given is uncertain and the condition for using binary search is that

89
00:07:44,450 --> 00:07:46,730
the input must be sorted.

90
00:07:47,910 --> 00:07:55,980
So what we will do is, first of all, we will sort the input, so let us first start the area so I

91
00:07:56,340 --> 00:08:04,590
a comma, a place and OK, so now that is sorted now by this actual work.

92
00:08:04,770 --> 00:08:05,490
So let's see.

93
00:08:07,010 --> 00:08:14,200
A number of elements, seven, and the elements are seven, six, five, four, three, two and one.

94
00:08:15,490 --> 00:08:16,960
So I want to search for seven.

95
00:08:17,890 --> 00:08:20,380
So key found at index six.

96
00:08:21,490 --> 00:08:24,210
So our output is coming out the right way.

97
00:08:28,700 --> 00:08:30,050
So this was the input.

98
00:08:31,090 --> 00:08:32,470
And I have converted.

99
00:08:33,740 --> 00:08:39,289
So after sorting, this will become one, two, three, four, five, six and seven, and I want to

100
00:08:39,289 --> 00:08:40,150
search for seven.

101
00:08:40,429 --> 00:08:42,980
So seven is present at index six.

102
00:08:43,250 --> 00:08:44,480
Seven is right.

103
00:08:44,510 --> 00:08:44,900
OK.

104
00:08:48,990 --> 00:08:54,510
So one more time now, this time I will give correct input that is sorted and put.

105
00:08:54,940 --> 00:09:02,240
So one, two, three, four, five, six and seven I want to search for let's save one.

106
00:09:03,450 --> 00:09:05,940
So we found at index zero.

107
00:09:10,620 --> 00:09:17,300
Number of elements are five and the elements are, let's say one, two, three, four and five while

108
00:09:17,300 --> 00:09:21,050
I'm giving and input, because this is the condition for using brain research.

109
00:09:21,890 --> 00:09:24,920
And I want to search for, let's say, four.

110
00:09:26,000 --> 00:09:28,640
So four is found at index three.

111
00:09:28,850 --> 00:09:30,950
So zero, one, two and three.

112
00:09:32,010 --> 00:09:40,920
Now, one more time, number of elements are five and the elements are, let's say, 10, 20, 23.

113
00:09:42,090 --> 00:09:51,570
25 and let's say 52, I want to search for 52 to be found and index for.

114
00:09:53,710 --> 00:09:56,430
Now, let us test minus one kiss, OK?

115
00:09:56,650 --> 00:09:58,030
When the game is not present.

116
00:10:00,240 --> 00:10:07,380
So there are five elements and the elements are twenty, thirty one, forty five, seventy eight and

117
00:10:07,380 --> 00:10:12,360
let's say a hundred, I want to search for 252.

118
00:10:13,500 --> 00:10:14,970
So key not found.

119
00:10:15,830 --> 00:10:19,350
OK, so I the searches working perfectly fine.

120
00:10:20,250 --> 00:10:22,890
Now one optimization we can do is.

121
00:10:26,460 --> 00:10:36,210
So focus on this part start plus and and then this is in record and then I'm dividing by two.

122
00:10:37,450 --> 00:10:40,990
What is the maximum value of integer intermix?

123
00:10:43,020 --> 00:10:45,840
OK, total the power, 31 minus one.

124
00:10:47,200 --> 00:10:49,100
So there may be a possibility.

125
00:10:50,650 --> 00:10:54,880
So suppose S and E are very big integers.

126
00:10:54,910 --> 00:10:57,930
OK, so Sandy are very big integers.

127
00:10:57,970 --> 00:11:00,130
My area is very big.

128
00:11:01,070 --> 00:11:02,620
OK, so it is very big.

129
00:11:02,830 --> 00:11:06,310
So, Sandy, the values of start and end are very big.

130
00:11:06,760 --> 00:11:13,000
So if you are adding two big integers, if you are adding to be contagious, there's a possibility that

131
00:11:13,000 --> 00:11:15,810
it may cross the valley of Intermix.

132
00:11:16,680 --> 00:11:19,390
OK, you are adding two very big integers.

133
00:11:19,390 --> 00:11:27,490
So there might be a possibility that this the sum of these two, that some of these two becomes greater

134
00:11:27,490 --> 00:11:28,510
than intermix.

135
00:11:29,270 --> 00:11:33,970
And if that happens, we call it integer overflow.

136
00:11:35,190 --> 00:11:43,860
Wraparound will take place, a wraparound will be there, and our output staff will become negative,

137
00:11:43,980 --> 00:11:46,860
very negative because the wraparound will be there.

138
00:11:47,490 --> 00:11:52,130
So this will start and will become negative and negative, divided by two.

139
00:11:52,140 --> 00:11:55,650
You will get a negative index, you will get a negative index.

140
00:11:55,650 --> 00:11:58,740
The value of it will be negative and then you will do this.

141
00:11:58,740 --> 00:12:03,150
AIFMD Ahmed made and maydays negative.

142
00:12:03,570 --> 00:12:06,760
You will get segmentation fault or you can see around Tamarrod.

143
00:12:07,710 --> 00:12:14,310
So if you will find it with the help of this method and start listening to what will happen ninety nine

144
00:12:14,310 --> 00:12:21,890
point nine nine percent, your goal is correct, but there might be integer or Florida Cancerian diameter.

145
00:12:22,350 --> 00:12:23,670
So how we can avoid it.

146
00:12:27,080 --> 00:12:38,390
OK, so tell me start plus and bitou, can I write like this, start plus and minus, start by two.

147
00:12:39,290 --> 00:12:40,430
So are the same.

148
00:12:42,400 --> 00:12:51,040
Let's see, so this value is start by two plus and by two, and these values start plus and minus,

149
00:12:51,040 --> 00:12:55,430
start by two, which is start by two plus and by two.

150
00:12:56,050 --> 00:13:02,800
So these so this value and this value, they both are the same.

151
00:13:03,100 --> 00:13:06,700
But in this case, you are adding two big integers.

152
00:13:07,090 --> 00:13:10,240
So they might be a possibility of integer overflow.

153
00:13:10,960 --> 00:13:16,730
And these are of low means crossing the maximum value, if you will, go ahead of intermix.

154
00:13:17,260 --> 00:13:19,320
We will call it overflow.

155
00:13:19,930 --> 00:13:26,170
But in this case, this is a big integer, big integer, and this is also a big integer.

156
00:13:26,170 --> 00:13:30,810
And you are taking the friends, OK, so you are taking difference.

157
00:13:31,060 --> 00:13:37,280
So in this case, overflow cannot be their overflow situation, can't be there.

158
00:13:37,780 --> 00:13:39,670
So this is much better.

159
00:13:40,730 --> 00:13:42,870
OK, so we will use it.

160
00:13:43,300 --> 00:13:45,500
We will always use it.

161
00:13:46,520 --> 00:13:50,290
Now, if we have overflow, that means we will also have underflow.

162
00:13:51,100 --> 00:13:54,610
So underflow means your value is less than the minimum.

163
00:13:56,080 --> 00:13:56,830
OK, so.

164
00:14:00,790 --> 00:14:02,290
So this is Intiman

165
00:14:04,750 --> 00:14:12,770
and this is and Max, so if you will cross over live into Max, we call it integer overflow.

166
00:14:13,240 --> 00:14:19,120
Similarly, if we will go beyond the minimum, I will call it underflow integer underfloor.

167
00:14:21,260 --> 00:14:27,960
So in this problem, in Dejour overflow mind, research into general flu might be there.

168
00:14:28,040 --> 00:14:32,310
So we have to handle this case also and how to handle this case.

169
00:14:34,070 --> 00:14:38,330
We will find made by another matter, which is Statler's.

170
00:14:40,270 --> 00:14:43,160
And mine is start by two.

171
00:14:43,700 --> 00:14:47,920
OK, so we will always find it with the help of this metal.

172
00:14:48,850 --> 00:14:55,390
Now, let's test this matter, number of elements are five and elements are one, two, three, four

173
00:14:55,390 --> 00:14:55,870
and five.

174
00:14:56,080 --> 00:14:58,320
I want to search for, let's say, two.

175
00:14:59,350 --> 00:15:01,340
So we found that index one.

176
00:15:01,390 --> 00:15:04,080
OK, so our goal is correct.

177
00:15:05,370 --> 00:15:11,040
So if you have any problem in binary search, you can ask me, OK, guys, so this is it for this video.

178
00:15:11,100 --> 00:15:11,610
Thank you.