Welcome back.
Let's now try to think how we can solve this question.
For this let's take a sample array.
So let's say this is the array which is given to us.
So let's write the indices.
So we have zero up to 11.
All right.
And let's say the target which is given to us is equal to five.
So we can see that we have five over here.
And then it goes on till here.
So the output should be four comma nine.
So let's try to see how we can do this.
Now again some of the things that we have to note over here.
First of all the array is sorted.
So it's sorted in non-decreasing order.
And then we also have to write a solution which runs in time complexity of O of log n as per the question.
So these are indications that we have to use binary search over here.
Now we will see how we will use a slightly modified version of binary search.
And we will use binary search two times for first time to find the left extreme, which is four over
here, and the second time to find the right extreme which is nine over here.
So we will use a modified version of binary search and we will use it two times.
So let's just walk through it.
So that's the best way to understand this.
So we are again going to have a left and right pointer which is pointing to the first and the last index
as we have in the case of binary search.
Now we are going to find the middle which is equal to floor of zero plus 11 divided by two which is
equal to five.
So middle is pointing to index five.
Now when we see that the target value is equal to the value at this index middle index, if it was not
equal, then we would have just proceeded with binary search as usual.
But the modification or the slight difference to the binary search happens when we find that the target
value is equal to the value at the middle index.
So it's from there that we are making some modifications to the binary search.
All right.
So we find that the target is equal to the value at the middle index.
So let's go ahead and modify binary search.
So let's see what we have to do.
So we have seen that the value at the middle index is equal to target.
Now let's first check if middle at this point is equal to zero which is the left most index.
If that is the case then we have found the left extreme.
And that would be zero itself because we cannot go any more left right.
So if middle at this point, when middle was the value at middle was equal to target, if middle was
pointing to index zero, then we don't have anything to its left.
And that's why we can say left extreme is equal to zero.
Now if this is not the case then we are currently over here.
Middle is pointing to this index right.
We're going to check the previous value.
So the value at index four.
So we are going to check if the previous value is equal to target.
Now if that is the case then we have to repeat the binary search on the left part.
Because we have not yet found the left extreme.
And repeating on the left part means nothing but setting right to be equal to middle minus one.
And then we proceed, whether recursively or iteratively, we are again going to go with the same logic.
All right.
Now if this is not the case, that is if the previous value is not equal to target, then we can say
that we have found the left extreme and that would be equal to middle.
For example, if middle was pointing to four, then we see that the previous value is not equal to target.
That means that this this index over here itself would be the left extreme.
So this is the algorithm that we will use to find the left extreme.
And we will have a slightly modified version of this to find the right extreme.
So let's go ahead and walk through the code.
So middle is now pointing to index five.
And we see that value at middle is equal to target right.
And we see that middle is not equal to zero.
So we are going to check the previous value.
And we see that the previous value in fact is equal to target.
Therefore we are going to repeat on the left part which means nothing.
But setting right is equal to middle minus one.
So let's do that.
So right is going to point to index four at this point.
And again we continue we are going to find the new middle which is going to be equal to zero plus four
divided by two which is equal to two.
So middle is going to point to two at this point.
Again we are going to check is the value at middle equal to target.
So let's try to see that.
We see that the value over here is three and the target is five.
So it's not equal right.
And then because it's not equal we are doing the same thing as we would do in binary search.
The modification only happens when the value at middle is equal to target.
So over here the value at middle is not equal to target.
So as in binary search we would just move left to middle plus one because target is greater than the
value at middle right.
So target is greater than three.
So let's move left to middle plus one as we would do in binary search.
And then we again find the new middle.
So the new new middle is going to be three plus four divided by two.
And then floor it which is equal to three itself.
Right.
So middle is going to point to three.
And then we are going to check the value over here the value is four and the target is five.
So we see that target is greater than four.
Or the value over here.
Hence we're going to move left.
The left pointer is again going to be moved to middle plus one.
So that is typical vanilla binary search right.
So again we move the left pointer to middle plus one.
And we are going to calculate the new middle.
Now the left and the right pointer is equal to four.
So middle is going to be four plus four divided by two which is four itself.
Now we see that the value at middle is equal to target which is five.
And we see that middle is not equal to zero because middle is equal to four.
And when we look at the previous value we see that the previous value is not equal to target right.
The previous value is four.
Therefore we have found the left extreme and we can just return four which is the left extreme which
is this index over here.
So this is how the modified binary search works.
So we have called the binary search modified binary search to find the left extreme.
At this point let's quickly recap what we have done.
So till we find the value at the middle index to be equal to target, it's the same thing as binary
search.
So we are going to have a left index and we are having a right pointer.
We find the middle.
And if the value is equal to the target then we are going to check whether middle is zero or whether
the previous value is equal to target.
So if middle is zero, then the left extreme is equal to zero.
But if middle is not equal to zero, and if the previous value is equal to the target, then we are
going to repeat on the left part.
So this is the repetition of the binary search on the left part.
And we do that by setting right is equal to middle minus one.
And then this keeps on happening and it will stop either when middle is equal to zero or when the previous
value is not equal to target.
In either case we would have found the left left extreme.
So this is how we find the left extreme.
Now let's proceed and take a look at how we can use binary search one more time to find the right extreme.
So let's go ahead.
And again we start.
We have the left index and the left pointer and the right pointer.
At the two extremes we find the middle.
So zero plus 11 by two.
When we floor it we get five.
So this is the middle at this point.
Now we see that the value at middle is equal to target.
So at this point we have some modification from the binary search.
Now if it was not equal we would have just proceeded normally as in the case of binary search.
That is we would move the left pointer or the right pointer.
So if the target would have been greater than the middle value, then we would have moved the left pointer.
And if the target is less than the value at middle, we would have moved the right pointer.
So that is normal binary search.
Now let's proceed over here we see that value at middle is equal to target.
Therefore we will check if middle is equal to length minus one which is the last index.
We see that that's not the case right.
Because if this is the case we can't move any more further.
Right.
And we would have found our right extreme which would be nothing but length minus one or middle.
Now, if this is not the case, we are going to check the next value.
All right.
So we will check if the next value is equal to target.
If the next value is equal to target then we have to repeat the same process on the right part.
So the right part means towards the right of middle right.
And repeating on the right part means nothing, but setting left is equal to middle plus one.
All right.
Now if this is not the case, that is, if the next value is not equal to target, then we would have
found the right extreme.
And the right extreme is just equal to middle.
So this is how the algorithm works.
You can see that the algorithm for the right part is pretty similar to what we have seen for the left
part.
Right.
The only difference is over here we are checking whether middle is the right most index.
And over here we were checking for zero.
And then for finding the left extreme we check the previous value.
But over here we are checking the next value.
So that's the difference.
All right so let's just walk through the code over here.
Walk through the algorithm.
Now at this point middle is pointing to five.
And we have seen that value at middle is equal to target.
So we are checking whether middle is length minus one which is 11.
No that's not equal right.
So we are going to check the next value.
So the next value we can see that that next value is also equal to target.
Therefore we have to repeat on the right part.
Now repeating on the right part means setting left is equal to middle plus one.
All right.
So left is pointing to six and right is at 11.
We are going to calculate the new middle which is six plus 11 which is 1717 by 217 by two gives us 8.5.
And then when we floor it we get eight right.
So we get eight.
So middle is pointing to index eight.
And again we are going to check is the value at middle equal to target.
Now at this point we see that it is equal.
If it was not equal then it's simple binary search.
Right.
We would move the left or the right pointer accordingly.
But over here because it is equal we are going to check is middle equal to length minus one which is
11.
No middle is eight.
And that's not equal to 11.
So we are going to check the next value is the next value equal to the target.
Over here we can see that the next value is five.
And yes we see that it's equal.
Therefore we have to repeat on the right part which is.
We are going to set left is equal to middle plus one.
So we have left at nine and right at 11.
Again we proceed.
We are going to find the middle value which is nine plus 11 by two which is equal to ten right.
Which that's equal to ten.
So middle is pointing at index ten.
Again we are going to check is the value at middle equal to target.
No it's not equal right.
Because it's not equal.
That is this seven over here is not equal to target.
Therefore we are going to check is it greater or less than.
Right.
So we can see that target is actually less than seven.
So target is less than equal to seven.
Therefore we have to move the right pointer to middle minus one.
So that is binary search right.
So that is how we implemented binary search.
So let's move the right pointer to middle minus one.
So you can see the left and the right pointer now are pointing to nine.
And middle is going to be nine plus nine by two which is nine itself.
Now again we check is the value at middle equal to target.
Yes it's equal right.
Because this is five and this is five.
Now we check is middle equal to length minus one.
Is it the last index.
No it's not.
Now is the next value equal to target.
No the next value is not equal to target because the next value over here is seven.
Right.
Therefore we come over here and we can see that we have found the right extreme which is equal to nine.
So the right extreme is equal to nine.
So we have found four and nine.
And we can just return four comma nine which are the extremes.
So this is how we are going to implement the solution.
You can see that the time complexity of this solution is going to be two times log n.
Why is that so O of two times log n.
Because we are calling two times the binary search right?
One time to find the left extreme, and then one more time to find the right extreme.
Now two is a constant.
So we can just avoid this.
And we can say that the time complexity of this solution is O of log n, and the space complexity is
going to be O of one.
If we implement this iteratively, and it's going to be O of log n if we implement it recursively because
of the call stack.
Now let's take a look at this.
For example.
Let's say this is the array which is given to us.
So you can see it's all five.
And then the target is also five.
So we make one call on the call stack where the left extreme is zero and the right extreme is seven.
So we are discussing about the recursive implementation of this.
Now the second call would be where we move right to middle minus one.
Right.
Because you can see that the previous value also is equal to five.
So we would move right to middle minus one.
And left will be at zero itself.
So this is the second call right.
Again we find the middle which is going to be one.
And we are seeing that that value is equal to target.
And the previous value is also equal to target.
So again we are going to move right to middle minus one which is over here.
And middle is also going to be pointing to zero.
And at this point we find again that middle is equal to zero.
So we have found the left extreme.
So you can see that we have called the function recursively three times and log of eight.
So we have eight elements over here log of eight is equal to also three right.
So eight is two to the power three.
So log of eight is log of two to the power three.
And this is equal to three right.
So that's why we can say that the call stack takes O of log n space space.
If we implement this solution recursively and the space complexity is going to be O of one.
If we implement this iteratively and the time complexity is O of log n, and yes, we have seen it can
be O of two times log n, but then two is a constant.
So we avoid it.
And we say that the time complexity is O of log.