Hey, guys, what's up?
So in the last video, I explained to you the concept of binary search.
Now in this video, we will see the code for binary search.
So the code for Vinessa is very simple.
What will I do?
First of all, I will take two variables and start, which is initially zero and end and which is and
minus one.
OK, so if I remember if I have an error.
So START was at the first start, was pointing towards the first index and this end was added last.
OK, so how many times find the mirror and compare.
So I told you will start is less than or close to the end.
So in the last video we have seen an example that if my start becomes than end then I can see that the
key card found ok, know found start and then end.
So I am doing the same Wildstar this list and I close to end.
What I will do I will find.
So Medical's start plus and by two now I will get married.
And now there are three cases.
So case number one, if the value present at mid is equal to the value that we are searching for, then
in that case I can return mid.
OK, I am returning the index.
Elusive, what I will do if the given value, if the value murder is greater than the value that we
are searching for, then I can say that my value, that my key will lie on the left hand side of the
mill.
So this is made all the values on the left hand side are less than made and all the values on the right
hand side are good.
So if this value is greater than guey, which is our second case, then my key will only lie here.
OK, so and it was made of minus one.
Similarly, as what you can do is start equals murder plus one.
OK, otherwise my answer will lie in the will lie in the right hand side.
So I will start equals one plus one.
So this is all that we have to do and when this will eliminate, OK, so when this valuable time made,
that means start becomes good, then end.
So this is the condition.
So I will reach her if I reach her.
And that means the value, the key is not present.
So I will return minus one.
OK, so if this Vilo terminate, if this may look damaged, naturally, what will happen.
So when this value will terminate, this will terminate.
When start will become guerdon.
And and if that is the condition we have seen in the last example that the key was not there.
So I will return minus one.
Minus one is an invalid index.
That is why I'm returning minus one side and returning an invalid index.
Otherwise, if the key is found, if this is the case, if the key is found, I will likely return made
to women, to the men and this whole program will be completed.
OK.
So this whole program is compared to this whole function is completed.
So let's write the code.
Let's say the name of the file is Binary Search.
Called Bindi's, which called for by new such binary search.
DARD cbb.
OK, so this was the call for leanness, which I am copying the whole code.
So this part will remain same, these things will be changed, so the delete.
They knew the function will also get changed, so the name of the function is binary search.
It will take three and put three arguments at a side of the array and lucky.
Now, I am taking input here, I am taking the value of key, and here I will call the function
bindery.
Serge.
OK, so Minnesota is taking three barometer's has been bought at a size of dairy and lucky, and it
will return the position at which the geese present.
If the operation equals minus one, then the key is not found.
Else the geese found at position Bewes.
Now, what I have to do, I have to first of all, I have to create two variables and start, which
is initially zero and and which is initially and minus one.
OK, so these are the two variables that I need initially.
Now, what do I want?
I need a loop and this loop will continue while the start is less than the close to end.
So first of all, I will find the value of it so intimately equals start plus and by two, OK.
Now the three cases, case number one, if the value present at mid is equal to the value that we are
searching for, then I can return mid.
OK, I'll see if I will check if the value presented is greater than the value that we are searching
for, then the value can only be present on the left hand side.
So and equals made minus one else.
I can see that my value will be present on the right hand side.
So start equals murd plus one.
OK, so this is all that we have to do.
And finally, if this value terminate you this way, terminate, that means that given key is not present.
In that case I will return minus one.
OK, so this is the whole court of binary search.
Now, al-Atassi.
OK, so Els, if.
So the number of elements are seven and the elements are OK.
So I'm giving unsorted input, so seven, six, five, four, three, two and one.
And the key that we want to find is seven.
So it is a returning key not found.
So by the surge is not working properly.
Why?
Because the input that we have given is uncertain and the condition for using binary search is that
the input must be sorted.
So what we will do is, first of all, we will sort the input, so let us first start the area so I
a comma, a place and OK, so now that is sorted now by this actual work.
So let's see.
A number of elements, seven, and the elements are seven, six, five, four, three, two and one.
So I want to search for seven.
So key found at index six.
So our output is coming out the right way.
So this was the input.
And I have converted.
So after sorting, this will become one, two, three, four, five, six and seven, and I want to
search for seven.
So seven is present at index six.
Seven is right.
OK.
So one more time now, this time I will give correct input that is sorted and put.
So one, two, three, four, five, six and seven I want to search for let's save one.
So we found at index zero.
Number of elements are five and the elements are, let's say one, two, three, four and five while
I'm giving and input, because this is the condition for using brain research.
And I want to search for, let's say, four.
So four is found at index three.
So zero, one, two and three.
Now, one more time, number of elements are five and the elements are, let's say, 10, 20, 23.
25 and let's say 52, I want to search for 52 to be found and index for.
Now, let us test minus one kiss, OK?
When the game is not present.
So there are five elements and the elements are twenty, thirty one, forty five, seventy eight and
let's say a hundred, I want to search for 252.
So key not found.
OK, so I the searches working perfectly fine.
Now one optimization we can do is.
So focus on this part start plus and and then this is in record and then I'm dividing by two.
What is the maximum value of integer intermix?
OK, total the power, 31 minus one.
So there may be a possibility.
So suppose S and E are very big integers.
OK, so Sandy are very big integers.
My area is very big.
OK, so it is very big.
So, Sandy, the values of start and end are very big.
So if you are adding two big integers, if you are adding to be contagious, there's a possibility that
it may cross the valley of Intermix.
OK, you are adding two very big integers.
So there might be a possibility that this the sum of these two, that some of these two becomes greater
than intermix.
And if that happens, we call it integer overflow.
Wraparound will take place, a wraparound will be there, and our output staff will become negative,
very negative because the wraparound will be there.
So this will start and will become negative and negative, divided by two.
You will get a negative index, you will get a negative index.
The value of it will be negative and then you will do this.
AIFMD Ahmed made and maydays negative.
You will get segmentation fault or you can see around Tamarrod.
So if you will find it with the help of this method and start listening to what will happen ninety nine
point nine nine percent, your goal is correct, but there might be integer or Florida Cancerian diameter.
So how we can avoid it.
OK, so tell me start plus and bitou, can I write like this, start plus and minus, start by two.
So are the same.
Let's see, so this value is start by two plus and by two, and these values start plus and minus,
start by two, which is start by two plus and by two.
So these so this value and this value, they both are the same.
But in this case, you are adding two big integers.
So they might be a possibility of integer overflow.
And these are of low means crossing the maximum value, if you will, go ahead of intermix.
We will call it overflow.
But in this case, this is a big integer, big integer, and this is also a big integer.
And you are taking the friends, OK, so you are taking difference.
So in this case, overflow cannot be their overflow situation, can't be there.
So this is much better.
OK, so we will use it.
We will always use it.
Now, if we have overflow, that means we will also have underflow.
So underflow means your value is less than the minimum.
OK, so.
So this is Intiman
and this is and Max, so if you will cross over live into Max, we call it integer overflow.
Similarly, if we will go beyond the minimum, I will call it underflow integer underfloor.
So in this problem, in Dejour overflow mind, research into general flu might be there.
So we have to handle this case also and how to handle this case.
We will find made by another matter, which is Statler's.
And mine is start by two.
OK, so we will always find it with the help of this metal.
Now, let's test this matter, number of elements are five and elements are one, two, three, four
and five.
I want to search for, let's say, two.
So we found that index one.
OK, so our goal is correct.
So if you have any problem in binary search, you can ask me, OK, guys, so this is it for this video.
Thank you.