Welcome back.
In this video we are going to try to understand the binary search algorithm.
So for this let's take a sample array.
So we have this array over here.
And let's say that the target for which we are searching is equal to nine.
So let's go ahead and write the indices of these elements in the array.
So we have the indexes from 0 to 9.
And we are searching for the value nine.
Now for the binary search we are going to have two pointers the left and the right pointer.
The left pointer is going to point to the left most index, which is zero, and the right pointer is
going to point to the right most index, which is nine.
Now we will go ahead and calculate the middle which is the floor of left plus right divided by two.
Now we could have done floor or ceiling.
It does not matter.
But we cannot take a decimal value.
That's why we have to either take the floor value or the ceiling value.
So over here let's go with the floor value.
Now zero plus nine divided by two is equal to 4.5.
And when we floor this we will get four.
So middle is going to point at index four.
At this point all right.
Now we are going to check whether the value at the middle index which is 11 is that value equal to nine.
So we see that array at middle over here which is 11 is not equal to nine.
All right.
So we proceed.
Now we go ahead and check whether the target value is it less than this value.
Or is it greater than this value.
Now over here we see that the target is less than the value over here.
Right.
So nine is less than 11.
So that means that the value, the target value if it is there in the array which is given to us, has
to be only on the left part.
Right.
It cannot be on the right part.
So this is the left part from the middle index.
And this is the right part.
All right.
So this is the middle.
Now because the target value is less than whatever we have over here.
It cannot be in the right part.
Right part because the array which is given to us is sorted.
Right.
So whatever is to the right of middle has to be greater than middle.
And we see that target is less than middle.
The value at middle right.
So we can straightforward eliminate this part.
And we are only concerned with the left part with respect to the middle index.
All right.
So for this we are going to move the right pointer from here.
We are going to move it to middle minus one.
Because we are only concerned with this part at this point.
Right.
So now left is pointing at index zero and right is pointing at middle minus one which is index three.
All right.
So now we are going to calculate again the new middle where left is this.
And right is this.
So you can see that the previous middle was over here.
And because the target was less than the value over here we have eliminated half of the input.
Right.
So this is the beauty of the binary search.
At every step we will eliminate half or almost half of the data which we have.
All right.
So over here we have 12345.
So these five values.
And then over here we have 1234.
Right.
And again 11 was the middle.
So we have eliminated this which is almost half of the remaining right.
So we already did a check whether target was equal to this value.
And we found it is not.
And then only nine values over here we have four.
And over here we have five right.
So total of nine values were remaining.
Now because target is less than the middle value we have eliminated these five values right.
So again this was already eliminated.
Plus another five values have been eliminated by moving the right pointer to middle minus one.
So this is the beauty of the binary search.
So let's proceed.
So left is now pointing to zero.
And right is pointing to three.
Again we calculate middle which is floor of left plus right divided by two which is equal to zero plus
three divided by two.
So you get 1.5.
And when we floor 1.5 we get one.
So middle is going to point at index one.
Now we again proceed with the same manner.
We are going to check whether target is equal to the value at index middle.
All right.
So the value over here is three.
So is nine equal to right middle.
Again we see that it's not equal right now at this point we are going to check whether the target value
is it greater than middle or less than middle.
Over here we see that nine is greater than three.
So nine is greater than array at middle.
So because of this.
So again this is the middle value.
This is the left part with respect to the middle value.
And this is the right part right.
So the remaining values have already been eliminated.
So we are only having these two.
So we already made a check with this value.
And we see it's not.
So this is also eliminated.
Now we need to decide whether we need to move left or right.
So we see that nine is greater than right middle.
So we know that everything to the left of middle has to be less than this value over here, because
the array which is given to us is sorted.
Right.
So we are no longer concerned with the left part.
So we are only going to check the right part.
For this.
We are going to move the left pointer to middle plus one.
So let's do that.
So we move left to middle plus one.
Middle was pointing at one.
So left is going to point at two.
And we are not changing right.
So right is pointing at three.
All right.
So now we are again going to calculate the middle value.
And again you can see that we eliminated the half right.
Almost half of the data is eliminated at every step.
Now the left pointer is pointing at index two.
And the right pointer is pointing at index three.
Again we calculate middle which is floor of left plus right divided by two.
So two plus three by two gives us 2.5.
And when we floor it we get two.
All right.
So middle is going to point at index two.
And we are going to again check and compare the target value with the value at middle index, which
is seven.
Right.
So are these two equal?
No.
We see that nine is not equal to right middle.
And we see that nine is actually greater than array at middle right.
So again what do we do.
We are only concerned to the right part.
So again we did not have anything to the left.
So the left is empty.
Now at this point we see that nine is greater than array at middle.
So we move right now if we had to move left we would have stopped right?
Because if, for example, we were searching for something over here, let's say six, right.
For example six.
In that case if target was six then we would have moved left, right.
So if we move left, then right would have been over here and left would have been over here.
So left is no longer less than or equal to right in that case.
And we would have stopped.
So that is the condition right.
So we will loop.
We will continue.
Either we are doing it iteratively or recursively.
So if we do it iteratively we will continue looping as long as left is less than equal to right.
All right.
Now let's proceed.
Now over here we see that nine is actually greater than the value at middle.
So we are concerned with the right part with respect to the middle index which is only this.
Right.
So we just have one more value left.
So what do we do.
We move left to middle.
Plus one middle was over here two.
So left becomes two plus one which is equal to three.
Now you can see left and right.
Both are pointing to index three.
Now again we continue.
We repeat the process we are going to.
And we have eliminated this.
Right.
Because we checked and we have seen that this is not equal to the value which is the target.
So you can see again we are eliminating half of the half of the input at every step.
Now let's proceed.
Left is three, right is three.
So middle is going to be three plus three divided by two which is equal to three.
So middle is also going to point at three.
And then over here we see that the middle value middle is at index three.
So the value at index three is nine and the target is also nine.
So these two are equal right.
So because they are equal we will return this index which is middle.
So we can just return middle.
And that's the end of our answer.
All right.
So this is how the solution works.
So you can see that at every point all we are doing is we are calculating the middle index.
And then we are going to check whether the target is equal to the middle.
All right.
The value at the index middle.
Now if it is equal then we return the middle index.
Now if it is not equal we are going to check is target less than the middle index.
If target is less than middle the value at middle index what do we do.
We move right to this part which is middle minus one.
And left does not change right now.
If that is not the case, if target is over here, that is, if target is greater than the middle index,
what do we do then?
Right is already in the beginning over here right.
So we are just going to move the left from here to here.
And then we can keep continuing.
That is how this function works.
Now we can implement this iteratively or recursively.
And we will see in the following videos how to do it in both the ways.
All right.
So if we are doing it recursively we are just going to have a helper function.
And at every step we are going to pass in the left and the right indices.
So that will depend on what part we are interested in and if not, if we are doing it iteratively,
we will again, we will just modify the left and right, and we will keep looping as long as left is
less than equal to right right.
For example, if left is, uh, greater than right, for example, we are searching for something.
Let's say we are searching for zero and the array is one, two, three and four.
At some point, the left and right is going to point to this index.
And we see that it's still not equal to the target value which is zero.
And then we will move left right because the value is less.
So we will move right to this part.
And at that point you can see right will be less than left.
And we can be sure that the value which for which we are searching is not there in the array which is
given to us.
All right.
So let's proceed and take a look at the complexity analysis of this solution.
Now the time complexity of this solution is going to be o of log n.
Why is that.
So again you can see the time complexity over here is O of log n.
Because at every step we are eliminating roughly half of the remaining elements.
Now this relationship over here is log n right.
So that's why the time complexity over here is log n.
Now you can also think of it in this manner.
If you double n then you just have to do one extra check to either find the value for which you're searching,
or to be sure that the value for which you're searching is not there in the array which is given to
you.
So let's take an example and try to understand this.
Let's say the array which is given to us is this 2021, 22 and 23.
And let's say the target value is ten right.
So let's write the indices over here.
Initially left is going to be equal to zero.
And right is going to be equal to three.
So middle is floor of left plus right divided by two right.
So middle is going to be one.
So we will see that they are not equal.
And we will see that target is less than this value.
So we are concerned with the left part right.
So we are going to move right to middle minus one.
So left and.
Right is going to point to zero, and then middle is going to be zero plus zero divided by two which
is zero.
So we get 20.
So we're going to check whether ten is equal to 20.
We see it's not equal.
And then we see that ten is less than 20.
So we will move right.
Right.
So we will move the right index.
So right will come over here and left will still point over here.
And then we see that left is no longer less than or equal to right.
And we can be sure that this value is not there in the array which is given to us.
So you can see that we made two checks, right.
We made a check over here when when left was at pointing to zero and right was pointing to three.
And then we made a check over here where left and right were pointing to zero.
So two checks right.
So we did two checks in this case.
Now let's double the size of the array to eight.
And let's say we are still searching for the value target ten.
All right.
So let's write the indices over here.
Now over here.
How many checks would we do right.
Initially the left and right pointers are at zero and seven.
So the middle would be at three.
So we do one check over here.
We see that it's not equal.
And we see that the target is less than this value over here.
So this much is eliminated right.
So left is still over here.
And right is going to be over here.
Right.
So left is at zero and right is going to be at two.
So zero plus two divided by two gives us one right.
So middle is going to be at one.
So we make this check over here.
And we see they are not equal.
So that's the second check.
So we see they are not equal.
And we see that ten is less than 21.
So we eliminate the right part.
Right.
So again right is moved over here.
So left and right will now point to index zero.
And the middle also is going to be at index zero.
So we are checking whether ten is equal to 20.
Again they are not equal.
So we move right to the left.
And at this point left is no longer less than or equal to right.
And we break out.
So again you can see we did three checks over here.
Right.
So for index zero one and zero.
So we did three checks when the size of the input was doubled.
So over here we had four elements and we do two checks.
Over here we have eight elements and we do three checks.
So this type of a relationship is also log n.
Right.
Because we know that log four is equal to two and log eight where from four we are doubling to eight
is equal to three.
That is we are only increasing by one.
So two plus one is equal to three.
So that's why the time complexity of this solution is equal to o of log n.
Now what about the space complexity.
Now the space complexity of this solution will depend on how we implement the binary search.
Now we can implement the binary search iteratively or recursively.
And in the subsequent videos we will see both ways of writing the binary search.
Now if we do it iteratively, the space complexity is going to be O of one or constant space.
Because we are not using any auxiliary space, we are not using, we are not creating a new array or
a hash map, etc..
So the space complexity is going to be constant space if we implement it iteratively.
Now, if we implement the same solution, the binary search recursively, then the space complexity
is going to be O of log n.
So let's try to understand why.
So over here we have this sample array.
And let's say the target we are searching for is nine.
So initially the left pointer and right pointer is going to be at zero and nine.
Right.
And we find the middle at four.
So this is in the first call right.
So in the first call it's going to be like this.
Now in the next call we are going to move the right pointer to middle minus one which is over here.
So left is going to be at zero.
And right is going to be at three right.
So in this manner we are going to call the helper function recursively with changing the left and right
pointers.
All right.
So the same function is going to be called with these two pointers at the second instance.
So the total number of instances at the same time in the call stack is going to be of the order of log
n.
So that's why we can say that the space complexity is log n.
So for example over here we have a total of ten elements.
So log ten when we flow this right.
Log ten.
When we flow this is going to be equal to three because log eight is three.
And then log 16 is going to be equal to four.
Right.
So log eight two log 15.
When we flow it is going to be equal to three.
Now let's try to understand over here we we've seen that there is going to be one call.
Let me just write the call stack over here.
There is a call where left is zero and right is nine.
All right.
And we are searching for nine.
Now we move in right over here in the second call and left is zero.
And right is going to be equal to three, and middle is going to be equal to over here one.
Right.
Again they are not going to be equal.
So we are going to move left to index two because target is greater than this three over here.
Right.
So left is going to be over here.
So the next call is going to be with two and three.
So index is going to be two.
Left index is two right index is going to be equal to three.
And the middle value is going to be two.
Again they are not equal.
So we are going to move left over here.
And we will make one more call where the left index is going to be equal to three.
And right index is also equal to three.
Right.
And then at that point we will see that yes target is equal to the value at middle which is middle will
be three at that point.
And the value over here is also nine right.
So over here you can see we have four calls on the call stack.
So we can say that the space complexity is going to be log n plus one because that's three plus one
which is four.
But then one is a constant.
So we can avoid it.
So we can say that the space complexity is of the order of log n.
So the time complexity is not going to change.
It's going to be O of log n itself over here.
Whether we do it iteratively or recursively, the time complexity is still O of log n, but then the
space complexity will depend on how we implement the solution.
All right.
Now again why is that so it's because we are using the space on the call stack.