Hey, guys, what's up?
So today we are going to learn binary search.
OK, so the problem with the Leena's search is that it doesn't take into consideration whether the given
area is Sadr or unsorted.
OK.
So we will use binary search for Sadr, that is.
So there's a condition, condition used by news such as that, and it must be sorted.
OK.
So binary search can only be applied if the given that is sorted.
If the ad is unsorted.
If I have unsorted.
Eddie.
Then binary search cannot be applied.
We have to apply linear search on leave.
OK, so linear search is the only option if we have unsorted erry.
But if we have sorted array, we will always use binary search.
OK.
So let's see.
So we will take an example and we will try to understand how binary search works.
So suppose my days.
So it must be sorted.
So let's see.
So these are indexes zero, one, two, three, four, five, six and seven.
And let's say the values are two, four, five, eight, twenty, twenty, three, forty and 49.
I'll get it.
These are the values.
For example, I want to search for let's say I'm undecided, vote for.
So how about in your search of works?
It takes two pointers.
So this is start.
And this is and.
OK.
So then it will calculate mid.
So Medek was start plus.
And by two now there's zero plus seven by two.
So three point five which is three.
So.
My mate is here.
Now, there are three possibilities.
So first, possibility, number one, if the value present that mid.
Is it close to the given value key?
If this is the case, I will have done made.
OK.
So I found the key and the key is present at the index mid.
Second possibility, if the value add mid is good.
Then that key.
So in this case, for example, it is a greater than four, then I can see that my answer, that key
will lie only in this part.
OK?
He cannot lie here.
So I will discard this part.
So what I will do.
And it was made minus one.
So my end will come here.
OK.
And how can I discard this part?
Because I know this is made.
All these were loose on the left hand side are smaller than mud and all the way loose on the right hand
side are greater than mud.
So these values are less than mid.
And these values are good.
Weird because my is sorted.
So if the value present at mid is greater than key, that means we can only only only lay in the left
part.
So I can discard the right part.
OK.
And similarly, if.
Murder is a less than key then.
So this is my murder.
This is right and this is left.
So right if I lose, Agard then moved.
So if my murder if developers entered Murd is listing key, then my answer will only lie in the right
part.
In that case, I will.
Ignored the left part.
And what I will do?
Start.
It was mid bless when.
So murder will come here.
So restart start will come here.
And my problem is, no, only this I have to search only on this part.
OK, so let's take an example and we will see what happens.
So.
So zero, one, two, three, four, five and six.
And the values are two, five, eight.
13, 15, 20 and 25.
And I want to search for value.
Let's say Geek was search for five.
OK, so first of all, this is a start.
This is my start.
And this is my.
And now I will calculate mid.
So Medek was start, which is zero plus and which is six by two.
So murders three.
Now this is my mid.
So compare the value is 13.
It closed five.
No, no check today.
Good.
Then five.
Yes.
The condition is true.
My answer will lie in the left part.
So I will discard this.
So and it was made minus one.
So that is three minus one, nerdish two.
So this is my end.
This is my end.
Now, I will again calculate mid, so mid equals start, which is zero, and which is two by two.
So it is coming out to be one.
So this is mid.
This is mid.
Now, again, I will compare is five it close to five.
Yes.
Then what I will do, I will return mid.
Return mid.
So I will return in next one.
OK, so this is how binary search look.
Now, in our district, when one example.
So I suppose the adays.
Zero, one, two, three, four, five and six.
And let's say that they lose out one, four, five, ten to an 18 and 25.
And I want to search for, let's say, twenty.
OK.
I want to search for value 25.
So this is my start.
This is my end.
First of all, calculate the mid so medicos start bless and buy two.
So Medical's three.
Okay, so this is my mid.
Now, compare is stand equals 25.
No.
The second condition is stronger than 25.
No less than 25.
I guess a middle value is less than key.
So I will search on the right hand side that is and equals.
So you start equals mid plus one.
So it values three plus one.
So this is four.
So now this is my updated start and I will discard this whole part.
Now, what I will do, I will conclude made again, so I made it because when Leo started this.
And there's six by two.
So Meredith's coming out to five.
So this is my mid.
Now, compare is 18, it goes to 25.
No.
Is 18.
Good.
Then 25.
No.
Is 18.
Less than 25.
Yes.
So what they will do.
Start equals mid plus one.
So murders five plus one.
So start equals six.
So discard the left hand side.
Now, this is my start.
OK.
Now I will calculate made again, so Medical's start, Blur's and by two.
So it is coming out to be six.
Now compare.
So is eight of six.
That is 25.
So is 25.
Equals 25.
Yes, the condition is true.
I will return mid and murders six.
So I will have done six and add the next six available and the five is present.
OK.
So this is out by new search work.
And now let us take one more example where the key will not be found.
OK.
So this is Mary.
Zero, one, two, three, four, five.
And let's see.
Six and seven.
And the values are two.
Three, four.
Eight.
Two.
Fifteen.
Twenty.
Twenty seven.
And the value that I want to search for is, let's say five.
OK, so five is not present here.
I want to search for five.
So this is my start.
This is my end.
Now let's call the valley of the.
Of Medical's start.
Bless and buy two.
So it is coming out to be three point five which is three and point upon integer will be an integer.
So this is my mind.
Now compare it to close five.
No.
Eight.
Good.
Then five.
Yes.
So what I will do.
And it was made minus when that is what is there.
You have made three.
So three minus one.
So.
And equals two.
So this is the new value off end.
And what I will do, I will discard the right hand side.
Now, again, calculate what is the value of mid, which is start bless and buy two.
OK, so two by two is one.
So this is my mid.
This is mid.
Now, compare the value of it.
So is three equals five.
No.
So is three.
Good.
Then five.
No.
So is three.
Less than five.
Yes.
So what I will do.
Start equals mid plus one.
So what is the value of made one.
So one plus one.
The value of start this two.
So start will reach here.
Now again calculate the value of mid which is start plus.
And by doing so four by two is two.
So this is my mid.
This is mid.
Now, what I will do, I will compare the values.
So is four equals five.
No.
Is four greater than five?
No.
So is four.
Less than five.
Yes.
So what I will do.
Start a course made plus one.
So what is there a love made murders.
Two.
Two plus one.
So Star Destry.
So my start will come here.
So this is my start.
Now, what happened is start is three and is two.
This is a start and this is and.
Okay, so what happened here is start becomes greater then.
And so if this is the condition, that means I can say I will stop and I will report that the key is
not present.
Key not found.
OK.
So if my start becomes an end, I will stop and I will report my answer that the given key is not present
in the area.
OK.
So this is how binary search works.
Now they're desperate to find how many number of steps by new search will take.
OK.
So what I am doing, I am calculating the value of limited riches start plus and Bitel and then I'm
comparing mid with key.
I am comparing these two values.
And each time I am comparing these values, what I am doing, I am reducing my number of elements on
which I have to search.
OK.
So if murd is a good denki.
And it was made minus one.
So if there are any elements.
So suppose there are any elements.
This is mid.
And if this mid is good denki, what I did.
I will put my point out here.
Where does it start?
And this is end.
So this is my new search space.
So this is my new search space given only be present here.
Otherwise you will not be there.
So initially I was searching on N elements.
Then I am searching on end by two elements.
OK.
And we will repeat the same process here also.
I will calculate murd.
I will compare key.
And similarly, if it is less dinkie, what I will lose start equals mid plus one.
So start will come here and I will discard this part.
So again, these are and by two elements only.
So what I am doing.
I am decreasing my search space by two.
So next time I will search on and buy four elements.
Then end by eight elements and so on.
OK.
So each time I am reducing my search of space, the search space means the number of elements on which
you have to search.
You have to perform search operation.
So what is happening here?
Initially, I have to search.
In N elements, then I will calculate, made and then compare.
Then I have to search in and buy two elements.
Then I have to search for and buy four elements.
I will search in and buy four elements for the glue and key, and it will keep going on.
Let's see the number of steps in bindings, which is key.
Okay.
Let's say here by new search takes K steps.
My minus such big key steps.
So finally end upon to the power key.
OK, so when this bisnis search will stop, when there is only one element in the area so.
And upon to a close one, that is this business which will stop only when there is only one element
in the area.
Because I cannot divide one element into two 1/2.
OK.
So in a quest to the power K taking log on both desires.
So log in it goes key log two and K equals log.
And with the base two.
And I told you that constant doesn't matters.
So Keiko's log off in constant doesn't Mattos.
So give us the number of steps.
And this is the log and so binary search, binary search takes log off and steps.
So what is the time complexity of binary search?
It is bigger off log in and linear search time.
Complexity of linear search was off.
And so this is for sorted.
Eddie.
OK, so if the given that is sorted, then binary search is a much, much efficient then linear search.
OK, so visited for this video.
And next video, I will write the code for by new search.
OK.
So if you have any doubt, feel free to ask.
Thank you.