Welcome back.
So this is the iterative version of the binary search which we have already written.
Now let's go ahead and code the recursive version of the binary search.
So let me just comment this out and let's go ahead and write the function over here.
So let's call our function binary search recursive.
Right now this function is going to take in again the array of integers which is numb's and the target
value.
Now once we are inside the function, we will be recursively calling the helper function.
All right.
So let's go ahead and write this function.
So const helper.
And this function is going to take in the array which is numb's and the target value and also the left
pointer and the right pointer.
All right now.
Again.
After we have completed writing this function, all we will be doing is we will call this function once.
So over here we will say helper and we will pass the array of integers, the target value.
And initially the left pointer is going to be zero.
And the right pointer is going to be the length of the array minus one, which is the right most index
of the given array.
So numb's dot length minus one.
All right.
Now again this function over here is going to either return the index where the target value is equal
to the value at that particular index in the given array, or it will return minus one.
So this function also the binary search recursive function also has to return that right.
So we will just say return whatever we are going to get back from this helper function.
Now let's go ahead and complete the helper function.
Now over here first we will check whether left is greater than right right.
So if left is greater than right we can just return.
So this is the base base case of the recursive call.
Right.
So we have returned minus one over here.
So at any point when we keep recursively calling the helper function and finally we reach the situation
that left is greater than right or left is no longer less than or equal to right.
Right if less is left is not equal to less than or equal to right, we can just say left is greater
than right, and when left is greater than right, we will just return minus one.
So that is our base case.
So let me just write that over here.
So this is the base case.
All right.
Now, if this is not the case, then we proceed further.
And first we are going to calculate the middle index.
So we can say const middle is equal to math dot floor.
Left plus right.
Divided by two.
And then we're just going to check whether the target is equal to numb's at middle index.
So let's check that.
So if.
Target is equal to numb's at middle.
Then we have found the target value and we can just return the index right.
So return middle which is the index at that point.
Now if this is not the case we have to check whether target is less than numb's at middle.
So if target is less than numb's at middle, in that case we just need to check the left part.
So we're going to recursively call the helper function.
And we are going to change the right right.
So we we want to keep the left as it is.
But then the right is going to change to middle minus one because we are only interested towards the
left part of the middle index in our array.
So we are just going to say return helper.
And now we are again passing the array the target value.
And left does not change, but right is going to be middle minus one.
So we're changing the right pointer.
All right.
Now if this is not the case that means numb's at middle is not equal to target.
And target is not less than numb's at middle.
So that means target is greater than num said middle.
So if that is the case we are only interested towards the right of the middle index.
So we're going to change the left pointer and we will make it middle plus one.
So in this case we are going to return helper.
And we are again passing the array numb's the target value.
And then we are going to change the left pointer to middle plus one.
And then the right does not change.
So right pointer stays as it is.
So that's it.
So this is the end of our function.
So what's happening over here.
We are again we have our helper function over here.
The helper function will either return minus one or a particular index.
Right.
And when we get that we are just returning that over here.
So that is what this function returns.
Now how does the helper function work.
The helper function.
Once we are inside over here it's checking whether target is equal to num said middle.
If so we will return that particular index which is middle.
Now if target is less than middle, we are recursively calling the helper function again.
And at this point we are changing the right pointer.
Right.
Now this call over here.
The interesting thing to note is over here is this call over here will either return minus one or a
particular index.
Right.
So if it is returning minus one again this whole function will return minus one.
And it will come over here.
And we are returning that minus one from this function.
So that's how this works.
Now let's take an example and let's walk through the code.
So again let's try first let's test our code.
So we have binary search recursive.
And let's say the array is again 1234 and five.
And let's say we are searching for the value ten.
So let's run our code and see what's happening.
So we are getting minus one, which is correct because minus one is not there in this array.
Now what if we change this to five?
So we get index four, which is correct.
Now what if we change this to one.
So we get index zero, which is also correct.
Now let's try to.
So we get index one which is this index over here.
So yes our function is working.
Now let's take an example.
And let's just walk through the code and see what's happening.
All right.
So we have this call over here.
Let's try to walk through the code and see what's happening over here.
So we pass this array over here to the binary search recursive function.
And the target value is equal to two.
Now we come inside.
So this is the definition of the helper function.
And then over here we are calling the helper function.
And let me just track this over here.
This is going to be our call stack.
All right.
So in the call stack we already have the binary search recursive.
But I'm not writing it over here.
We'll just track the helper function.
So this is the first call to the helper function.
All right.
And at this point the left index is going to be zero.
And the right index is going to be numb's dot length minus one.
So the length over here is five five minus one is equal to four.
So we are calling it with zero and four.
So once we are inside the function we are checking whether zero is greater than four.
That's falsy.
So we don't go inside over here.
And then we are going to calculate middle middle is going to be zero plus four divided by two which
is two at this point.
And then we are checking uh let me just write the indices over here 0123 and four.
So middle is pointing over here.
And we are checking this value whether it's equal to target.
So over here we have three right.
So this is three.
And we can see that three is not equal to two.
So it won't go inside over here.
Then we come to the next line of code.
We are checking whether target which is two is two less than three.
That's truthy.
So again we are going to return whatever we are going to get back from this call.
Right.
So we have the next helper call over here.
So this is the recursive call.
And at this point we are again passing the array.
We are passing the target value left is not changed.
So left is still zero.
But right is going to be middle minus one.
And middle was two right.
So two minus one is going to be one.
So we are calling the helper function with zero and one.
So again we are inside the function over here.
So let's just clean this up.
And left is equal to zero.
Right is equal to one.
Now we are checking whether zero is greater than one.
That's falsy.
So we come inside over here and we are doing zero plus one divided by two and flooring it right.
So zero plus one divided by two gives us 0.5.
And when we floor it we get zero.
So middle is going to point at index zero.
And then we are checking whether target which is two.
Is it equal to this value over here at index zero which is one.
Right.
So two is not equal to one.
So we don't go inside this line of code.
So we come over here and we are checking whether target which is two is two less than one.
No that's false.
So we don't continue with this line.
So we come over here and you can see that we again call the helper function recursively.
And now we are changing the left pointer to middle plus one.
And middle was zero right.
So middle plus one is one.
And the right pointer does not change which is one itself.
So the helper function is again called with the left index as one and the right index as one.
So again we come inside the function over here.
So let's clean this up.
And left is equal to one.
And right is equal to one.
At this point.
And we are checking whether one is greater than one.
So that's falsy.
So we don't return minus one.
So we come over here and again we calculate middle which is one plus one divided by two.
So at this point it's going to be one itself right.
One plus one by two gives us one itself.
So middle is index one.
Now we are checking whether target is equal to the array which the array which is given to us at index
one.
Right.
So let me write the index over here 0123 and four.
So at index one we have two.
And the target value also is equal to two.
So these two are equal.
So when we are doing this call right with one and one we will return middle value.
So this call over here which is with one and one will return the index one right middle over here is
one.
So it will return one.
So this function also will return this back right.
So we get one over here as well.
And this call which was the first call which happened over here.
This call over here is also going to return this one over here.
That's how the function the binary search recursive function is going to return one.
And that's our answer over here.
So that is how this function works.
Now let's take a quick look at the space and time complexity over here.
So the time complexity is again O of log n.
Why is that so.
Because again it's the same reason why we discussed previously as well.
So at every step we are eliminating half of the input because we are only looking at one part, either
the left part or the right part.
Right.
So either it's equal.
Otherwise we are going to change.
If the target value is less than numb's middle, we are changing the right pointer.
So we are only looking at the left part.
Now if that is not the case, we are changing the left part and we are only looking at the right part.
So we are eliminating half of the input at every step.
So that's why the time complexity is going to be O of log n.
Now the space complexity is going to be O of log n as well over here because this is a recursive function.
Right.
So in the worst case, in the worst case we are going to have log n calls on the call stack at the same
time.
So that's why we can say that the space complexity is going to be O of log n, where n is the number
of elements in our given array.
For example, we had over here.
Five elements.
And again remember this.
We have we have to floor this over here we have five elements.
So if you do log five and if you just floor this you can see that we are going to get two.
Now over here you can see we had three recursive calls of the helper function.
So we are just approximating it to log n right.
We could say it's log n plus one.
All right.
Because we have three over here.
But then again one is a constant.
So we can avoid it.
And we can say that the space complexity of this solution is O of log n.