Welcome back.
Let's now go ahead and write the iterative solution to find the range of the target value in the array
which is given to us.
So let's call this function search for range iterative.
And this function is going to take in the array.
And the target value.
All right.
Now, once we are inside this function, we are going to have two variables left.
Extreme.
And right extreme, and let this be equal to what we get back from two other functions so left extreme
and right extreme respectively.
So left extreme is going to be equal to what we get from find left extreme function.
All right.
And this function also is going to take in the array and the target value.
And right extreme is going to be what we get back from the find right extreme function.
And this function also takes in the array and the target value.
And then we are just going to return an array.
Where the first value is left extreme and the second value is right extreme.
All right.
So this is how we will approach this question.
Now we need two functions over here because the pointers are moving in different directions when we
want to find left extreme and right extreme.
So that's why.
So we could write it out in a big single function.
But this is just to break the break the code into different parts and make it more readable.
So let's go ahead and write the find left extreme function first.
So we have const find left extreme is equal to function.
And this function takes in the array and the target value.
Now once we are inside it, let's say left is equal to zero and let right be equal to the right most
index, which is array dot length minus one.
And let's initialize the middle variable.
All right.
Now we are going to have a while loop.
And this will keep looping as long as left is less than right less than equal to right.
So this is pretty much similar to how we implemented the binary search iteratively.
So once we are inside the while loop we will calculate middle.
So middle is going to be equal to math dot floor.
Left plus right divided by two.
And then we will check if target is equal to array at middle.
Now.
If it is equal, we will make some modifications to the binary search.
So over here we have some modifications.
Compared to binary search.
All right.
So modified binary search.
Now, if it is not equal, then we just proceed, right?
So if if target is not equal to right middle then we are going to check if target is less than right
middle.
And if that is the case, then we only have to look towards the left part of the middle index so we
can say right is equal to middle minus one.
And if this is not the case, it means that target is greater than right middle.
And we can just say left is equal to middle plus one because we only want to look towards the right
of middle.
Now once we are out of this while loop.
And if we were not able to return anything over here, we will just return minus one, which means that
the target value is not there in our array.
All right.
Now let's proceed.
So if target is equal to array middle let's complete this part.
We have to check if middle is equal to zero right.
If middle is equal to zero then there is nothing before it.
And if array at middle is equal to target, that means we have found the left most extreme.
So in that case we can just return zero.
So the left extreme is going to be equal to zero.
Now let's proceed.
If this is not the case then we will just check if the previous value that is if array at middle minus
one.
Is equal to r, a is equal to target.
All right.
So if the previous value is equal to target then we have to look towards the left part.
Which means we have to set right equal to middle minus one.
And then we keep looping again as long as this is true.
Now if this is not the case that is if the previous value is not equal to target, then also we have
found the left extreme and we can just return middle, which will be the left extreme because the previous
value is not equal to target.
And we know that the array which is given to us is sorted.
So this is how we will find the left extreme.
Now let's go ahead and write the right extreme function as well which is find right extreme.
So let's write it over here.
Const find right extreme is equal to function.
And this function is going to take in the array and the target value.
Now, once inside the function, let's say let left is equal to zero and let right is equal to array
dot length minus one.
And we initialize the middle variable.
So let middle and we'll have our while loop.
And this will keep looping as long as left is less than equal to right.
So this is similar to binary search.
Now once inside the while loop we will calculate middle which is math dot floor.
Left plus right divided by two.
And then once we have middle, we are going to check if target is equal to array at middle.
So if it is equal, then we will have some modifications over here compared to binary search.
Alright.
Now if it is not equal then we are going to check if target less than array at middle.
If that is the case, then we only need to look towards the left of the middle index and we can say
right is equal to middle minus one.
And if this is not the case that means target is greater than array at middle.
And we need to look only towards the right of middle.
So we can say left is equal to middle plus one.
And finally we also have to return minus one over here.
That is the case where we come out of the while loop without returning anything.
So returning minus one means the target value is not there in our array.
All right.
Now let's proceed and complete this part.
So if target is equal to array at middle we have to first check if middle is equal to array dot length
minus one which is the right most index.
If that is the case and target is equal to array at middle right because we are inside this if condition.
So then we have found the right extreme and we can just return middle or array dot length minus one.
So that that means the right most element is the right extreme of the target for that particular target
value and the array given to us.
All right.
So if this is not the case then we are going to check if the next element that is array at middle plus
one.
Is equal to target.
So if the next element is equal to target, then we have to continue looking in the right part to find
the right extreme.
So we're going to say left is equal to middle plus one.
And 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 just return middle which is the right extreme in that particular case.
So this is how the function works.
Let's now go ahead and test our code.
So we'll call this function.
And let's pass in an array over here.
And the target value.
So let's say the array is one comma, two comma, three comma, three comma, three comma, three comma,
four comma five.
And let's say we are searching for three.
So let's run our code and see what we are getting.
So we are getting two comma five.
So this is index 2012.
That's correct.
And this is three four and five.
So two comma five is correct.
Now what if we were searching for nine.
Let's run the code.
We get minus one comma minus one because nine is not there.
That's also correct.
What if we are searching for one.
Let's try that and we get zero comma zero which is correct.
Which is just this one value over here.
Right.
So our code is working.
Now let's take this sample over here and let's run through the code.
Walk through the code where we are passing this array and the value three.
All right.
We are calling the function search for range iterative.
And this array is passed to it.
So I've just written it down over here.
So we come over here and we are calling the find left extreme function to find the left extreme and
the find right extreme function to find the right extreme.
And then it's just returned as an array.
So let's walk through the find left extreme uh function over here.
So the array is passed to it and the target value is equal to three.
Now left is set to zero.
So left is pointing over here.
And right is point to set to array dot length minus one which is equal to seven.
So right is pointing to seven.
And then we see that left is less than equal to right.
So we're going to calculate middle.
So middle is going to be zero plus seven by two.
And then we are flooring it.
So we are getting middle to be equal to three.
So middle will point at index three.
And then we are seeing that target is equal to array at middle right.
So three over here and three so these are equal.
So we come inside this if condition.
And we are checking if middle is equal to zero.
No that's not the case because middle is three.
And over here we are checking if the previous value is equal to target.
So we see that the previous value is equal to target because this is also three.
So we are setting right to middle minus one.
So right is going to be over here which is index two.
All right.
Again we come over here.
We see that left is still less than equal to right.
So in this iteration we are again calculating middle which is zero plus two by two which is equal to
one.
So middle is going to be equal to one.
So middle is pointing to index one.
At this point.
Now we are checking if target is equal to array at middle right middle is equal to two.
Target is three.
So these are not equal.
So we come over here we check if target is less than array at middle target is the greater value.
So we come over here and we said left is equal to middle plus one.
So left is also going to point over here.
Right is also pointing over here.
So again we come over here we see that left less than equal to right is truthy because they are equal
at this point.
And we calculate middle as left plus right by two which is two itself.
So middle is going to be equal to two.
And we are seeing that target is equal to array at two.
Right.
So this is equal to target.
So we come inside this we check if middle is equal to zero.
No that's not the case.
We check if the previous value is equal to target.
That's not the case because the previous value is two right.
So we come to this else over here and we are just returning middle which is equal to two.
So that's how we find that the left extreme is equal to two.
Right.
So let's see that.
So this function over here returns two.
Therefore over here right when it returns to left extreme is going to be equal to two.
And that's what we are returning in this array over here.
So left extreme is two.
Similarly we will find the right extreme as well.
So let's go ahead and take a look at that as well.
So let me just clear this up a little bit.
All right.
So we are inside the find right extreme function.
And the array and the target value is passed to it.
And again left is set to zero.
And right is set to the right most index which is array dot length minus one.
All right.
And again the target is three itself.
So left is over here and right is over here.
And we come inside the while loop.
And we calculate middle which is equal to three.
So middle is over here.
Now we see that it's equal.
So over here we are checking if middle is the last index is middle equal to array dot length minus one
which is seven.
No that's not true.
So we come over here and we are checking if the next element is equal to target.
Yes the next element is equal to target.
Therefore we are going to set left is equal to middle plus one.
So left is going to be over here.
And then again we come over here we see that left is less than equal to right.
So we calculate the new middle.
So seven plus four is 1111 by two is 5.5.
And we floor it.
So middle is going to be equal to five.
Again we see that target is equal to right middle.
And we come inside.
We see that middle is not the last index.
So this is middle at this point which is five.
And over here we are checking the next element is the next element equal to target.
No that's not true.
Right.
So we come over here and we are going to return middle which is equal to five.
So that's the right extreme.
So that is how we are finding the left extreme and the right extreme.
So we just now we saw that this over here is going to return five.
So that's going to be the right extreme.
And previously we have seen that the left extreme this function over here is going to return two.
And that's going to be the left extreme.
So this is how this function works.
Now let's take a quick look at the space and time complexity.
So the time complexity of this solution is going to be O of two times log n.
Because we are calling one time binary search to find the left extreme and one time binary search to
find the right extreme.
Now this is a constant, so we can just avoid this.
The time complexity is O of log n, and the space complexity is O of one or constant space.
Because we are not using any auxiliary space that can scale with the input scaling.
So the time complexity is O of log n and the space complexity is O of one.