Hello all and welcome back.
So in this video let us continue our discussion.
And now let's learn about binary search.
So in binary search again just like linear search we will be given an array okay.
So we will be given an array or a list.
And we have to find the target.
One very important thing to note in binary search is that our array will always be sorted.
So what do we mean by sorted.
Either the element will be in the increasing order or they will be in the decreasing order.
Okay.
So it will not be a random array.
Just like we took in a linear search, binary search can only be applied on a sorted array or list.
Okay, so that's the very first prerequisite very important to check before applying the binary search.
So let us take an example.
Everyone let's say we have been given this array.
Okay.
The elements are ten, 23, 35, 45, 50, 70 and 85.
Great.
Now, say the target which I have to find is 50.
What I use the logic which I used in binary search is to use this sorted property of my given input
list.
Right?
So because I know that this is sorted, what I do is I follow this particular approach.
First and foremost I will.
Consider.
The full array okay.
So we are considering the full array or list.
How do we do that?
I am saying that I will be taking a low which is equal to zero and a high, or we can maybe take it
as start and end.
That will be better.
So I will be starting from zero and end will be at.
N minus one.
So n is the length here.
So I am saying that hey I am starting from here and my end is here.
So this way we are considering the whole array or list given to me right now.
In the next step I just see the middle element.
See the middle element.
How can a fine middle?
Everyone?
I can just say middle is going to be.
End minus start.
Divided by two.
Okay.
We normally take this floor division.
So if you remember, let me just show you one thing so that you have the quick revision.
If I'm doing print five divided by two, I will get 2.5.
But if I use this sign two times floor division.
Okay.
So along with in our operators we must have studied the floor division.
Operator.
This will be two because we will just be taking the integer part.
It is very important.
Please make sure that you always remember this thing.
Because we cannot have in a list or an array an index which is decimal.
I cannot ask you to give me the two point the number at 2.5.
Right.
So this is zero one, two, three, four, five and six okay.
Great.
Now the next step.
What I do is in the third step.
Third we compare.
Element at mid element at middle with target with target.
Okay.
So in the example which we are taking everyone the middle we are going to find is going to be three.
So this will be the middle initially right.
This is the first iteration here if you will see what's going to happen.
Middle is 45 okay.
So in the first iteration if I have to write iteration.
Middle is three.
Middle is the index okay.
And array of middle is 45.
Now just pause the video and think for a moment.
Do you think that if I am trying to find 50 and middle is 45?
And I am also saying that this whole array is sorted, it is going to increase in this particular direction.
Okay.
Do you see that we can find our middle in the left half of my array.
So if I take these two halves first half and second half, because the array is sorted, I can be sure
that each and every thing, each and every element which is behind this middle element is going to be
smaller than my target.
Right?
So in this case our target again is 50 okay.
Which is less than 50.
So we can be sure of very much sure that we will not find in this full Half are element, and that's
the major idea behind binary search.
Using this property of the array being sorted, I try to just reject the half each and every time.
So instead of going through each and every element like we were going in linear search, I will just
be changing how much array I am considering at each iteration.
Now what's going to happen?
So pay attention everyone this time, because I know that middle element is smaller than the target.
I will move my start here.
Okay, so let me just draw it once again.
I'm going to move my start here.
Once we move our start here in the next iteration, in the second iteration, start will be here and
end will still be there only okay.
And I will keep on repeating this unless either my start becomes greater than end or I am able to find
my element.
Okay, so in the next iteration, what is going to happen?
Everyone?
This time this will be the mid.
This will be the mid.
Okay.
So let us see for the second iteration.
Second iteration.
This time the middle is five.
Okay.
So it is four.
This is six.
It's going to be five six minus four two okay.
And two divided by two one.
So middle is going to be oh sorry.
This will be end plus start.
My bad start plus end by four.
Right.
Or end by two.
So six plus four 1010 by two five.
So my middle this time is five.
Everyone now at five if you will see the array at this mid is 70.
Now the same understanding kicks in that if I am standing at 70, everything is increasing at this side.
I have to find 50.
I will never be able to find 50 on the right side.
Doesn't matter how long my area is okay.
You will never be able to find anything here, so we have to make sure that we move our end this time,
okay?
Because it is greater than 50, we will move our end this time.
So the end is going to become middle minus one.
It is going to come here.
Finally start and end.
Both are at the same position.
Start end.
Both are equal to four.
Four plus four by two.
Middle is also going to be equal to four okay.
So four plus four divided by two is equal to four only right.
So this time I am at middle again.
Now if you see in the third iteration.
Third iteration.
Middle is for and this time we have found the element array of mid equals 50 which is equal to my 50.
So we have found our element.
What does that mean that yes we are able to successfully using binary search say that this element is
present and we are going to return mid.
So our whole aim is to make sure that at each iteration we are able to get rid of half or half of our
array.
Okay.
Now this is only working if our array is sorted.
If it is not sorted then we have to resort to linear search only majorly.
It is a lot faster than linear search.
You will see one thing here as well.
In three iteration I am able to find my answer.
If there would not have been any this particular element.
Let's say we were finding 55.
Then in the next iteration, I would have made start equal to n plus one.
This is what we did here, right?
So we were increasing the start greater than this particular thing.
So after that what I can say that it is not present.
So I will return minus one because start will become greater than end.
So in a list you are saying that hey start from this which is ahead from it which is not possible.
So the start and end are just your variables which we are using to see how much array we are considering.
Okay, so that's the whole logic.
You are able to see that how in three iteration we are able to do that.
If we would have done similarly linear search here we must have to do six iteration at least because
I can ask you to find 85 as well.
Right.
So we are going to have this discussion in the further module where we will be discussing in depth about
the complexity.
Okay everyone.
So don't worry on that.
But yeah we can see that in the starting as well, that it is faster, comparatively faster than my
linear search.
But again the array should be sorted.
Okay, great.
So now let us see the same in action and write the code for that as well.
Let us quickly write the code.
And I have to also explain you one thing as well.
We can also think of this in terms of a intuitive problem.
So in this problem let's say the students are standing in an assembly.
Okay.
Let's say you are a new teacher who have come to a school.
Students are standing in an assembly.
If you will be able to visualize.
Now let's say you want to find this particular student, okay.
And there are many students like you are not able to see each and every one of them in binary search.
What you are doing is you are going to this particular student because he is in the middle right now.
I hope you will be able to see that how everyone is bigger than this particular person.
So you will be surely finding your student in this half and never in this particular half.
So each and every thing here is not of use to you.
So you have get rid of the half of your overall list or an array.
Okay, this is the major visualization part, which I want to make sure that you always remember.
Just try to basically see that how it is in real life.
Okay, so because you were here, everything above is bigger.
You will have to now search just in this space.
So your search space is getting shorter and shorter.
Okay.
Let us just try to visualize this again in multiple things.
So in all this course you will see that I will be focusing a lot on visualizing that you are able to
visualize each and every algorithm.
So I found a very good overall website through which we can see that how exactly things are going to
happen.
So again 1023 3545 5070 and 85 and say, I want to find 50.
Let us see this, everyone.
What's going to happen?
See, it's saying element found an index for in the first iteration the lower bound was zero.
The upper bound was six.
Middle was three something which we did similar when we compared.
We have to now make sure that we increase our lower bound.
Lower bound will now go here.
So see the red color everyone.
This time lower bound is here.
Higher bound is here.
Upper bound is here and midpoint is 70.
Now this time also, because 70 is greater than 50, we will have to reduce the overall upper bound.
And this time both are all are equal to four.
And my element is also found.
So I can return that.
Let us just try to do for 55 and let us find this.
It is saying element cannot be find in the list.
Again, same things are happening.
Okay.
But finally it has to stop because the last element is also not equal to 55, just to see how it will
work for ten.
Okay, so let's pay attention everyone.
See for ten initially zero middle and high okay.
So this is the upper bound lower bound.
And this is the middle.
This time in iteration two we will be moving this upper bound okay.
So we have to see what we have to move.
That is the condition also which we will write.
We are this time moving this upper bound here which we can see in this particular diagram.
Lower bound is zero.
Upper bound is two.
This is the mid.
It is still not equal.
And thus we will do the third iteration and we will reach ten here okay.
So great everyone I hope I hope that this is also clear.
Now let us try to code this out.
Let us remove this and let me keep this only so that you remember this particular thing.
Okay.
Great.
So first our sorted list we have to take.
Let us take the same example 1023 3545, 5070 and 85 okay.
Target is 50 and result is binary search sorted list.
And the target okay.
Let us write the code for this.
Everyone.
This function it is not able to find and we should print our result as well.
Okay.
Let me just get rid of the output window one second and let me zoom in as well.
Great.
So let us now define this binary search function.
Here again I will be getting a overall array and a target.
So the problem statement is same I am getting an array and a target.
Okay, cool.
Let us find the size of my array.
Length of array minus one.
Now start can be zero.
End can be size minus one.
Okay, so just like we talked here in this particular dry run.
So this is what dry running the code is where you are seeing that how values are going to change.
So you will find that values are changing at these steps.
Let me just underline them as well.
Let's say maybe the red color.
So you understand this okay.
Let's use this color only.
So this is where the values are changing.
So this is what we have done.
We have dry run our code.
Now what exactly we have to do next everyone is to define our start and end.
So start is zero.
End is minus one.
Now we have to do this in iteration.
If we have to use iteration, then I think all of us know we have to use the loop.
Right.
So let us use the looping.
While.
Okay.
So we have studied about while loop as well.
Low is sorry.
Start is less than or equal to end.
Now this condition is very important.
I am going to just run this loop until start is less than or equal to N, because the second starts
become greater than end.
Then of course it is an invalid array.
Here also we saw that at the end start and a lower bound and upper bound they were becoming the same.
Okay great everyone.
So now let us see what exactly we have to do in our dry run, which we did here.
We were finding the middle.
So let us do the same thing.
Middle is equal to start one minute.
Yeah.
Start plus end.
and we have to make sure to put this brackets and for Division two.
Okay.
So this is how we can find the middle.
Very first thing I used to check if my array of mid is equal to target right.
If it is equal to target for example let's say I find 45 here in a single iteration we will find this
right.
So 45 is on the middle only.
So if I am able to find then I don't need to change anything.
Right.
I don't need to then increase or decrease my array which I'm considering.
So that means I can just return the mid found the target right?
Else if Elif my mid okay is greater than target, which I'm looking forward to.
So this time what I'm saying, let's say I am trying to find 23 and this time my mid 45in the first
iteration it is greater than target.
So 23.
I am trying to find 45 is the middle.
Then I am sure that I will not find it in the right side.
So what I have to reduce.
Think on this once and have this in your mind.
We have to reduce the higher bound, the upper bound.
So upper bound will become mid minus one.
We have checked on mid.
We are sure that from mid to upper bound this will not be there.
So upper bound the end here will be mid minus one and else.
Or we can write Elif here also so that each and everything is handled array of mid it is less than target.
Okay so let us see this as well everyone.
Let's say I want to find 70 This time I want to find 70.
In the first iteration mid is 45.
The array at mid is 45.
I know 70 is bigger.
Okay, so I'm sure that this is not going to have my 70 here.
Can you now think what exactly we have to change this time?
I think it will be lower bound because we have to.
Now just look in this particular thing, we cannot change the higher bound as of now.
So our start will be mid plus one, exactly the same way we have discussed in our overall design as
well.
Start and end.
We have changed here right?
In these overall iterations we have changed.
Let me just do one thing so that your notes are more better.
So let me just change the color of this particular.
Theory so that you are able to understand that this is the overall algorithm.
Okay.
Great.
So now it is fine.
This is red.
One is the dry run and this is the algorithm.
Okay, everyone.
Now if we have completed our loop and we are still not able to find anything at MIT, then in the end
I can return minus one.
Okay, so great everyone.
Now let us try to run this once and it says that you are able to find 50 at for a very good way to check
your algorithm, which I discussed with you in the problem solving basic as well is to check for these
boundary condition.
So for ten let us run this.
It is able to find on zero.
For 85 it is able to for 85 see for 85 one second.
Let us see why is it giving an error.
Yes.
So we have taken this size length minus one okay.
So we have to make sure.
So see I'm not I'm don't have to take the size length minus one size is this only.
And I have to take it size minus one here Also size is seven.
There are seven elements, but end is seven minus one, which is six.
In the starting upper bound is six.
Okay, so this was a mistake.
Now we were able to catch this mistake because we were checking for boundary condition, something which
I told you in the problem solving as well.
Right.
So make sure that you follow that framework.
And now if I run this see I'm able to find this at six.
So I hope everyone this is now clear.
You are able to understand that how exactly binary search works.
Now what you have to do for me is you have to work it out for another example, and you have to draw
everything along with that.
I have shown you a visualization here to always remember this.
It's a very important algorithm.
Just try to run this on Python Tutor as well and see how the visualization will go.
Okay so great everyone.
So I hope this is clear.
Always remember the visualization and also try to code this once at your end.
So let's meet in the next video.
Thank you.