Hey, guys, what's up?
So in the last we do, I explained to you the concept of binary search.
Now in this video, we will see the code for binary search.
So the Cornford business, which is very simple.
What do I do?
First of all, I will take two variables and start, which is initially zero and end and which is N
minus one.
OK.
So if you 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 middle and compare.
So I don't lose.
Vital start is less than ordered close to end.
So in the last we do, we have seen an example that if my start becomes good then.
And then I can see that the key not found.
OK.
Kinnard found f start.
Good then.
And so I am doing the same Wildstar this less than close to end.
What I will do I will find mid.
So Medek was 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 it close 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 estimated 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 mud.
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 downward.
So if this middle value is greater than guey, which is our second case, then my key will only lie
here.
OK.
And equals murder minus one.
Similarly, as what you can do is start equals murder plus one.
OK.
Otherwise my answer will lie in.
The key will lie in the right hand side.
So I will start equals mid plus one.
So this is all that we have to do.
And when this wire loop terminated.
OK.
So when this rare look will damaged, that means start becomes good, then end.
So this is the condition.
So I will reach here if I reach here.
That means the value.
The key is not present.
So I will return minus one.
OK.
So if this Vilo terminated this way look damaged naturally.
What will happen.
So when this my love will terminate.
This will terminate.
When start will become good then.
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 am returning minus one.
So I am returning an invalid index.
Otherwise, if the key is found, if this is the case, if the key is found, I will direct later turn
made to these men, to these men.
And this whole program will be completed.
OK.
So this whole program is comprised of this all function is completed.
So let us write the code.
Let's say the name of the file is Binary Search.
Caught by new search, called for by new search, binary search.
Dart, CBP.
OK, so this was the court for leniency, which I am copping the whole gold.
So this part will remain same.
These things will be changed.
So delete.
They know the function will also get changed, so they know the function is binary search.
It will take three and put three arguments, every side of the Eddie and the key.
Now, I am taking input here.
I am taking the really off key and here I will call the function
binary.
Serge.
OK.
So by is taking three barometer's as input at a size of dairy and the key, and it will return the position
at which the geese present if the pollution equals minus one.
Then the key is not found as the geese found at Perdition Buick's.
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 N minus one.
OK, so these are the two variables today need initially.
Now, what do I want?
I need a loop and this loop will continue.
Violet Start is less than articles to end.
So first of all, I will find the value of my ID so intimate a equals start plus.
And by two.
OK.
Now the three cases.
Case number one.
If the value present at mid is a close to the value that we are searching for, then I can return mid.
OK.
Elusive.
I will check if the value is impaired, made is greater than the value that we are searching for.
Then the value can only be present on the left hand side.
So end 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 VI looked at it this way, looked at it, that means that given key is not present,
in that case I will return minus one.
OK.
So this is the old guard of binary search.
Now, let's see.
OK, so El's, if.
So the number of elements are seven and the elements are OK.
So I am 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 returning key not found.
So by any searches, not working properly.
Why?
Because the important that we have given is unsorted.
And the condition for using by search is that the input must be sorted.
So what do we lose is, first of all, we all saw the input.
So let us first start, Eddie.
So I thought a comma, a plus and OK, so now that is sorted now by any such rule book.
So let's see.
Number of elements are 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 somewhere.
Output is right.
OK.
So one more time.
Now, this time, I will give correct input.
That is sort of the input.
So one, two, three, four, five, six and seven.
I want to search for let's have one.
So we found at index zero.
Namaroff elements are five and the elements are, let's say, one, two, three, four and five.
Why am givings ordered and bought?
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.
A number of elements are five and the elements are, let's say 10.
Ten.
Twenty three.
Five.
And let's see.
Fifty 52.
I want to search for 52, so key found at legs for.
Now, let us test minus one case, okay?
When the gays not present.
So there are five elements and the elements are 20, 31, 45, 78 and Lenzi handled.
I want to search for 252.
So key not found.
OK.
So by new 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 into Max?
OK.
Due to the power today, one minus one.
So there may be a possibility.
So suppose S and E are very big integers.
OK, so S&P are very big integers.
My area is very big.
OK, so my area is very big.
So S&P, the values of start and end are very big.
So if you are writing two big integers, if you are writing to be contagious.
There's a possibility that it may cross the value of intermix.
Okay.
You are adding two very big integers.
So there might be a possibility that this the sum of these two.
Now, 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 star plus and will become negative.
Why negative?
Because the wrap around will be there.
So this really start plus end will become negative and negative.
Divided by two, you will get a negative index.
You will get a negative index.
They will live mid, will be negative.
And then you will do this.
AIFMD of made and made is negative.
You will get segmentation fault.
Or you can see it and Tamarrod.
So if we will find murder with the help of this method start.
Listen to what will happen.
Ninety nine point nine nine percent.
Your code is correct, but there might be immediate or flawed.
Who can say it and diameter.
So how we can avoid it.
OK, so tell me start.
And by two, can I start like this?
Start plus and minus.
Start my.
So are these same.
Let's see.
So this value is stark way to bless, and I do.
And this values start bless.
And where do minus start?
By two, which is start by two plus.
And why two.
So these.
So this value and this value, they both are same.
But in this case, you are adding two big integers.
So they might be a possibility of integer overflow and bizzaro flow 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 in danger.
And this is also a big and danger.
And you are taking dear friends.
OK.
So you are taking difference.
So in this case, overflow can cannot be there or a flow situation can 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 into minimum.
OK.
So.
So this is Intiman
and this is.
And Max, so if you will cross over live into Max, we call it in Egypt overflow.
Similarly, if we will go beyond A.M., I will call it underfloor and deja underfloor.
So in this problem in Egypt or flaw by any search and digital flow might be there.
So we have to handle this case also and how to handle this case.
We will find made by another method, which is start.
Plus.
And minus start by two.
OK.
So we will always find mid.
With the help of this method.
Now, let's test this method number of elements out of 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 a court is correct.
So if you have any problem in buying this search, you can ask me.
OK, guys.
So this is it for this video.
Thank you.