Now, if you will pay attention here, everyone, you will find that we have actually, in a way, reduced
our problem, right?
Reduced our problem.
And that has actually reduced in a similar manner.
So initially I said that, hey, start from the full array and end towards the full length of the array
and find an element x.
But now what I have done, what I have done is I have reduced my problem.
I have reduced the size of my problem where I am asking to just find in this particular part of the
array or a list, right?
So this is the whole understanding, of course, about the binary search.
And if you have able to think like this, if you are able to think like this, then doing it or changing
it into recursion should be easy.
So now let us see how exactly that's going to roll out.
So the very first thing which you will find is that in binary search I am just getting the list and
the element to be found.
We are not talking in terms of start and end.
So for that, for that what we can do is we can create a helper function.
Now this is again something which we have already discussed.
So I can create a helper function.
And in this helper function now I am actually returning everything.
Now I am just sending everything right.
So let me create this helper function.
Great.
L1XS and e right.
So the reason of course I have created this helper function is because I needed to send something more
towards my argument or sorry towards the parameters of my function.
And I have already discussed that how we can do the same.
One thing always remember more questions.
You do more.
You will understand where you need to create this helper function.
That is the first thing.
Second thing is that yes, you could have created default arguments, but here it would have been a
little difficult, right?
You will have to create the length of L one, but we are making sure that we always send L one.
Right?
We are not sending the copies of array.
So L one is going to change.
So in this question you would not have been possible.
And we should be aware about this helper approach.
This might seem a little bit difficult in initial few questions, but as and more you practice, this
will become a lot more clear.
Okay, now if I try to write my code for binary search, of course, first thing is if my S is greater
than E, if my S is strictly greater than E, then I can return false because in this case, what is
happening in this case, what is happening is something like this one second.
That I am saying that I am.
My start is somewhere here and my end is here.
Then of course this is not possible, right?
If my start is here and end is here, I am actually in a way kind of giving you a negative size array.
Or the array of course, is basically this is not a valid array.
Right.
Valid valid list we are starting is after the end.
So that's why we can return false okay.
The same thing we have actually seen I think in the iterative flow as well.
Next is we have to find our middle.
We have to find our middle.
So middle we have already seen we can find like this.
So taking the float division so small small thing.
This is where it is used.
Now if L one and I think I missed one more thing.
I missed this index.
Now let's say, yeah, we can change the that's the beauty of helper function that we can take index
here right now M and M is there.
Okay.
Sorry.
My bad.
We don't need to have this M.
We need to find out, not index.
My bad, I got confused.
We have to use an M only.
And if this is equals to X, then I can return true.
Then I can return true.
And now you have to pay attention.
So earlier we were updating.
We were updating our small and end in iteration in this code only right in the for loop only.
Now in this specifically, we are now sending S and e the updated position in this particular function's
parameter.
So understanding is going to be the same.
Just that we are going to reduce our problem.
So if my x is greater than middle middle element then what should I do.
So what I am saying is what I am saying.
Let us take an example here.
If, let's say I am trying to find trying to find five and this is for the middle is four, right?
As you can see here.
Now, of course, five is something which is greater than four.
So I should found in the right side.
I should found on the right side to make sure that I am finding on the right side I should actually
have my s the starting element at middle plus one.
So what I'm going to do, I'm going to call this again.
I'm going to call this again.
So I'm just going to do return binary search.
And I should just make M plus one right.
I hope this is clear.
Everyone just I am transforming the iterative understanding to recursion.
And if that's not the case, like if that is not the case then I can just do x.
S can be as it is, but m is going to be now m minus one.
So for example, if I would have been finding two and the middle one is four.
Now I know that okay, this is the part where it is going to be right.
This is the part where it is going to be.
And I think that makes sense.
Right?
I have to now remove or actually shrink my boundaries in this manner.
So start is going to be at one only, but end is going to get shifted to three, right?
Again, all this has been done, but I am still making sure that I explain you each and every step so
you can understand.
These initial problems are a lot important to grasp the power and understanding of recursion, and I
think this makes our code complete.
Now if you are thinking that why I didn't check else here with an if statement.
The reason because I'm returning because I'm returning here, right?
Because I'm returning here.
This statement will only get executed when this is going to be false.
So that's the reason I didn't check it like this right?
In each and every statement, I am just returning directly.
So it does not matter if I am calling that afterward as well.
So instead of this having this Elif kind of a statement, I can just have it like this directly.
Okay?
And now I think this code will work.
One second binary search using recursion takes two position argument.
So this is something which we are calling here.
We are passing the list and this right.
Let us see where the error is.
And L1X0 and length of l one.
So where exactly it is giving the error?
Let us see quickly everyone.
Binary search using recursion takes two positional argument, but four were given.
Okay my bad I think.
Yeah, I am not calling it over.
Yeah, so we were actually calling this not the helper one.
So four arguments were there and it is only expecting two right.
But we have to call this function only now it is able to say that okay I am able to find five here.
Let us find 400.
Let it update one second.
Let it save.
So it is saying list index out of range.
Okay this is strange.
That is quickly check.
Where have we made an error.
So it is M plus one and E and this is okay.
My bad.
We have to send this length of L1 minus one right.
That is something which you have to send.
So I send the length which of course is at the end.
So somewhere the start is going to move towards end.
And finally we are going to get list index out of range.
That thing is very important.
So always make sure that you first do this on paper or somewhere where you are writing your logic or
understanding your logic, and then transform it into code instead of directly jumping into the into
the code.
Now, I made sure that this is what I am taking as e, so the whole code is actually written with that
in mind.
Again, something which I explained to you when we were doing iteration, right?
So yeah, now I think this will work.
Just one thing which I would like to show you, which I think all of you are anyway aware.
But if, let's say even our element is this big, even our list is this big.
And let's say if I pass L1 here, we are not going to face any problem here because this is binary search.
We have seen that how it is very fast, very much fast than your normal searching.
Right.
The linear searching.
So we are not going to get any problem, any error in the module which will follow, we will be properly
discussing about in terms that okay, why is this faster.
And about this time and space complexity of this particular function as well.
Right.
So then you will be able to actually appreciate that okay.
How powerful binary search as an algorithm is.
and we can see the same here as well.
Right.
So how quick it is.
Right.
See to find it.
So great everyone.
I hope the binary search again is now also clear.
Please make sure that you understand this subtle helper things and how we are actually transforming
the whole understanding into code.
I never suggest to run behind solution.
You can always write a solution by looking or by, I would say understanding in gist.
Like let us say you saw a video and writing it.
The problem happens to understand and write it afterwards or after some time.
So that is why I always make sense that I am spending this particular time.
Now what I will expect is that you are going to make a recursion tree for this, and also run this particular
code on Python tutor, or try to basically make the visualization yourself as well so that your understanding
is top notch.
Okay, so now in the next video, let us focus on sorting algorithm which are specifically done using
recursion, namely the merge and the quicksort.
So I am going to again make sure that I explain you that properly.
But before that please make sure that you do practice on this particular code because the understanding
is going to get used in that as well.
Okay, cool.
Then everyone let's meet in the next video.
Thank you.