Welcome back.
Let's now go ahead and implement the solution that we discussed to find the range of the target value
which is given to us in the array.
Now first let's go ahead and implement this in the recursive manner.
For this we will need a function.
Let's call it search for range.
Recursive.
And this function is going to take in the array which is given to us, and also the target value.
Now inside the function, let's say const range is equal to an array with the values minus one and minus
one.
And we are going to call two functions.
So these are going to be recursive functions.
So let's call one find left extreme.
And this function is going to take in the array the target value and the range.
And it's going to modify the range if it finds the target value.
All right.
So it will modify this.
And then let's have one more function let's say find right extreme.
And this function also is going to take in the array and the target value and the range.
And it will modify the right extreme which is this value over here in the array of this in the range
array.
And then finally we will just return the range.
So this is how we will implement it.
So let's go ahead and write these functions.
So let's start with find left extreme.
Now this function, as we have seen, is going to take in the array the target value and the range.
Now once inside the function let's first write the base case.
So this is going to be a recursive function.
All right.
So we will call this function again if required inside the function.
Now the base case is going to be if left is greater than right right.
So if that is the case then we can know that the target value is not there in the array which is given
to us.
And we can just return in that case.
So we will just return.
If left is greater than right we will just return.
Now if this is not the case let's proceed.
So we will calculate the middle value.
So middle is going to be math dot floor.
Left plus right.
Divided by two.
So this is going to be the middle index.
Now let's go ahead and check if the value in the array at this particular index is equal to the target.
So if array at middle.
Is equal to target.
If this is the case, then we proceed.
All right.
So as long as this is not achieved, as long as we have not re, uh, found the target value at the
middle case, it's going to be same as binary search.
Right.
So over here if that if let's just continue.
So we will come back and fill this over here.
Now if the value at the middle index is not equal to target.
So we are just going to check is target less than the value or greater than the value.
So if target is less than array at middle.
In that case we have to call this function again recursively.
But we are going to look at the left part, right.
So we are going to pass the function the parameters array target.
Range, and then we'll have to change the left and right index.
So over here also we'll have those right.
So we'll have left over here as well.
So let's initialize it to zero.
So if it's not passed it will take the value zero.
So we don't need to modify it over here.
And then right is going to be array dot length.
Minus one, so if it's not passed, it will just take this value.
So we don't need to modify it over here.
But in this case we have seen that target is less than the value at the middle index.
So we have to look only in the left part.
So we are going to change the value of right.
All right.
So the value of right is going to be middle minus one.
So let's go ahead.
So left is not changing.
So left is as it is.
And then right is going to be middle minus one.
Because we only want to look towards the left of middle.
Now if this is also not the case that is if right middle is not equal to target and right middle and
target is not less than right middle, that means target is greater than right middle right.
So if that is the case again we will recursively call find left extreme.
And then we will pass the parameters array target range.
And then we only want to look towards the right of the middle.
So we are going to change left to middle plus one.
The parameter left is going to be middle plus one.
And then right does not change.
All right.
So this is how the function works.
Now let's go ahead and complete this part over here.
Now if we have found the value that that is right middle is equal to target.
In this case we have to check first if middle is equal to zero.
So if middle is equal to zero then we cannot go towards the left right.
So that means that we have found the left extreme.
And we can say range at index zero is going to be middle or zero.
Right.
So I am just writing zero.
So at this point middle is equal to zero.
So I can write either way.
Now if this is not the case that is if middle is not equal to zero then we have to check if the element
to the towards the left, that is, if the element at index middle minus one is equal to the target.
So let's check that.
So else if array at middle minus one.
If this is equal to target, then we have not yet found our left extreme right, so we have to continue.
If this is the case, then we have to continue calling the function recursively.
So we'll say find left extreme.
And then we have to look towards the left part.
So let's pass the parameters array target.
The range and we want to look towards the left part.
So left does not change and right becomes middle minus one.
Right now.
If this is not the case, that is, if the element towards the left of the middle middle index is not
equal to target, then we have found our left extreme right.
So if this is not the case.
So let's write.
So else we have found our left extreme.
And we can say range at zero is going to be equal to middle.
Because whatever is left to this index is not equal to the target.
So we have found the left extreme.
All right.
So this is the find left extreme function.
Now let's go ahead and write the find right extreme function as well.
So here we say const.
Find right extreme.
And this function is going to be pretty similar to the previous previous function with some modifications.
So again this function also takes in array target range.
And this also will take the pointers left and right.
So left is equal to zero and right is equal to array dot length.
Minus one.
Now, once inside the function again, we start with the base case.
So the base case is if left is greater than right so if left.
Greater than right now.
In this case, we can just return.
All right.
So that's the base case.
Now if this is not the case we proceed.
So we'll say const middle is equal to math dot floor.
Left plus right.
Divided by two.
So we find the middle index.
Now we are going to check if array at middle is equal to target.
So let's just keep this over here.
Now if it is not equal then it's just simple binary search.
All right.
So we proceed.
So else if target is less than array at middle.
If this is the case then we look towards the left part right.
So we can recursively call the same function find right extreme.
And we're going to pass the parameters array target.
Range and we want to look towards the left part because array is less than the middle value.
So left does not change and right becomes middle minus one.
Now if this is not the case, that means target is greater than array at middle.
So if target is greater than array at middle, we are again going to call the same function recursively.
We pass the parameters, but we want to look towards the right part because target is greater than array
at middle.
So array target.
Then we pass the range.
And because we want to look towards the right, left is going to change to middle plus one.
And then right does not change.
All right.
Now let's come and finish this part over here.
If array at middle is equal to target we are first going to check if middle is the right most index
of the given array which is given to us.
So if middle is equal to array dot length minus one.
So that means we are at the right most index and we cannot go any further.
Right?
Right.
That means we have found the right index.
So in this case we can say range at one is equal to middle.
Because middle is equal to right length minus one.
So we can say either range at one is equal to middle or range at one is equal to array dot length minus
one.
Now let's proceed.
If this is not the case then we check if the next element that is at the element at middle plus one
index is equal to the target, so else.
If target is equal to array at middle plus one.
Then we have to call the function recursively and look towards the right to find right extreme, and
we pass the parameters array target range.
And we want to look towards the right.
So left is going to change to middle plus one and right is remaining as it is right.
Now if this is not the case that is if the next element is not equal to target, then we have found
the right extreme and we can say range at one right, which is the which is denoting the right extreme
is equal to middle.
All right.
So that brings us to the end.
So we have done we are done with writing the function.
So we have written find right extreme function which is recursively called.
And we have written the find left extreme function.
And we are calling both of these over here.
And it will change these values of the range array.
And then finally we are just returning the range array.
So let's go ahead and test our function.
So we have this function let's call it.
And let's pass in an array.
So again the first parameter is the array and then the target value.
So let's go ahead and pass in an array.
Let's say one comma one comma 2223 and four.
And let's say we are looking for the value two.
Now our expectation is that it should return the indices of this and this right.
So this is zero one.
This is two this is index two three and four.
So two comma four is what we expect.
So let's go ahead and run the function and see the output.
All right.
So we have an error.
So let's just check it left is not defined.
So somewhere instead of left I have written left.
So let's see that.
All right.
So it's that over here it should be left.
Now let's again run this.
All right.
So we are getting our output two comma four.
So this is our index 2012.
Yes that's correct.
And this is index four.
So this is correct.
So we are getting the right answer.
Now what if we were looking for one.
Let's see.
So we'll get zero comma, one zero and one.
That's correct.
Which is these two.
Right.
These two indices.
What if we were looking for the value for.
We get six comma six which is this index.
Right.
So this is 012345 and six which is correct.
And what if we were looking for let's say five.
It should give minus one comma minus one.
Right.
Because five is not there in the array.
And yes that's correct.
So this function is working correct.
So let's go ahead and see how this is working.
Now let's say we are calling the search for range rect function.
This is the array that we are passing to it.
And the target value is equal to two.
So let's now see what's happening.
So we are over here.
And range at this point is minus one comma minus one.
And then we call the find left extreme function the array the target value and the range is passed to
it.
All right.
So we are over here.
And at this point left is equal to zero.
And right is equal to array dot length minus one.
So let me just trace the call stack over here so that we can understand this better.
All right.
Because this is going to be a recursive solution right.
So at this point left is equal to zero and right is equal to array dot length minus one.
The length over here is 34567.
So seven minus one is equal to six.
So right is equal to six.
All right.
Now is left greater than right.
No right because left is zero and right is equal to six.
So we come over here we calculate the middle value which is zero plus six divided by two which is equal
to three.
And then we are checking if array at middle is equal to target.
So let me write the indices over here 012345 and six.
So these are the indices over here.
And you can see that yes array at index three is two right.
So it's equal to two.
So we come over here.
Now we are checking if middle is equal to zero.
No middle is equal to three.
Right.
So we don't go further.
We come over here.
We are checking if the previous value that is array at middle minus one is equal to target.
So this is middle minus one.
So we see that it's equal to the target two.
So yes it's true.
So we recursively call the find left extreme function.
Again at this point left is going to be zero but right is going to be middle minus one which is two.
Right three minus one is equal to two.
So let's write that over here.
We are calling the function again at this time left is zero and right is equal to two.
Now let's clear this up.
So we are again inside this function over here and left is equal to zero.
Right is equal to two.
And we see that zero greater than two.
That's false.
So we don't return.
We come over here and we calculate middle which is zero plus two by two which is equal to one.
So middle is equal to one.
And now we are going to check if right middle is equal to target.
No that's not true.
Right.
So one over here is not equal to the target two.
So we come over here.
Now is the target less than right.
Middle.
No.
Right.
Because target is two and right middle is equal to one.
So we come over here and we call the function again recursively.
And at this time we are going to make left to be middle.
Plus one middle is equal to one right.
So this is going to be two.
So left is going to be two.
And right is right itself which is two.
So we are calling the function with two comma two.
All right.
So let's again come over here.
Now we are again over here and you can see that left is two, right is also two and middle will be two,
middle will be two.
And we see that right middle is equal to target.
So this is truthy.
We come inside.
Middle is not equal to zero.
And we see that the previous value is not equal to target right.
So therefore we can say that range at zero is equal to middle.
So we are going to change this.
This is range at zero right.
This is going to be changed to middle which is equal to two.
So that's how we get two over here.
So this call over here will just complete right.
So this will be just a recursive call over here.
Uh I think it was part of this right.
So once this is over it will just finish.
It will just return and this call will just expire.
Similarly, this call also will just finish wherever we came, wherever we did this call.
Right.
So it will finish once this is over.
This call also is just going to finish because we are not returning anything.
So this will also come finish and it will come out of the call stack.
Similarly this also will come out of the call stack and we are done right.
So in this way we will find the left extreme to be equal to two.
And we get two comma minus one at this point.
So let's just change this over here we have two comma minus one at the current moment the range.
So again let's take a look at the main function.
So let's clear this up.
All right, so we are done with this call.
Now we are going to call this find X right.
Extreme.
All right.
So let's go to that function.
And again we are calling the function.
And we are not passing the left and the right.
So left is going to be zero.
And right is going to be array dot length minus one.
So we know the length over here is seven.
So that's going to be six right.
Is going to be six.
Left is zero.
So let's.
Trace that over here.
So we have the call with zero and six.
And then once inside this we check this left is not greater than right.
So we come over here we calculate middle to be three and then array at three.
Array at three is equal to the target.
We have seen that over here.
So we come inside.
Middle is not equal to array dot length minus one.
Right middle is equal to three.
So we come over here and is the next value equal to two.
That's what we are checking over here.
We see that yes that is true.
Right.
So yes because of that we are going to make another recursive call over here.
So let me just write this in red and we'll keep it over here so that we can see what happens once it
returns.
So at this point left is going to be middle plus one which is four.
All right.
So left is four and right is going to be six.
And we make this call.
We are again inside the function.
All right.
Now left is not greater than right.
So we calculate middle which is four plus six is ten.
Ten by two is equal to five.
So middle is equal to five.
Now mid array at five is not equal to target right.
So it's not equal.
So we come over here is target less than array at five.
Yes.
Target is less than array at five.
So we are calling the function recursively over here.
So at this point left is going to be as it is.
So left is four itself.
But right is going to be middle minus one.
Middle is five.
So right is going to be four itself five minus one is four.
So we are having this recursive four call with four comma four.
Again.
We are inside over here.
Now.
At this point, middle also is going to be equal to four because that's four plus four by two.
And we are checking whether array at four is equal to target.
So we see yes that's the case.
Array at four is equal to target.
Now over here we are checking if the next element is equal to target.
So middle plus one.
That's this one over here.
And we see it's not equal right.
So it's not equal.
So we come over here and we said range at one is equal to middle which is four.
So we are going to change this value to four.
Right.
So that's how we get two comma four.
In this way we have found the range.
And then this will just expire and this will expire.
And finally this also will expire.
So this is how we are finding the range.
All right.
So let's take a quick look at the space and time complexity of this solution.
So the time complexity of this solution is going to be O of log n right.
Again, we could write two into log n because we're doing it two times over here, but then two is a
constant so we can avoid it.
All right.
So the time complexity is O of log n.
What about the space complexity.
Now the space complexity is also O of log n because this is the recursive solution.
And we will be using space on the call stack.
So each time the maximum space used in the call stack will be of the order of log n.
So over here also we may use log n space.
And over here also we may use O of log in space.
So the space complexity is going to be O of log n.
And again we cannot say it's two into log n because this is at a time right.
So we we want space used in the call stack at a time.
So this this will just return and it will just expire.
Right.
And then we come over here.
So the space complexity is O of log n.