Welcome back.
In this video, let's try to think how we can solve this question for this.
First let's develop some intuition regarding the solution.
So over here let's take an example 123456.
And let's go ahead and write all the possible rotations for this array which is given to us.
So one possibility is 612345 right.
Another possibility is 561234.
Then we can have 456123 and 345612 is another possibility.
And finally we also can have two, three, four, five, six and one.
So these are the various possibilities.
Now over here this is index zero.
This is index one.
This is index two.
This is index three.
This is index four and this is index five.
Now previously like we have seen in the case of binary search we will be finding the middle value which
is left plus right divided by two.
And then we are floating it.
So over here that would be zero plus five divided by two which is 2.5.
And when we float it we will get two.
So the middle value is going to be at index two.
So let's just circle the middle value in all of these possibilities.
So these are the various cases.
Now let's make an interesting observation.
If the left value the value at the left index.
If this value over here is less than the value at the middle index, then you can see that the left
part is always sorted.
For example, over here you can see that one is less than three and this part is sorted.
Similarly, four is less than six.
So this part over here is sorted right.
Similarly three is less than five.
So this part is sorted two is less than four.
So this part is sorted.
So we will make use of this property to solve this question.
Now if this is not the case that is if left is the value at the left index is not less than the value
at the middle index, which is the case for example over here.
Right.
You have six over here and two over here or over here.
You have five over here and one over here.
So in these two cases you can see that the right part is sorted.
So if this is not the case then the right part is sorted.
So this is an interesting observation.
So in these two cases these sections are sorted which is the right part.
Now you will also see that this part over here 456 is also sorted.
Similarly five six is sorted and 123 is sorted.
This is the case where the left value is less than the middle value.
So we know that the left part is sorted, but you can observe that the right part is also sorted.
But we cannot use this to solve this question because this is not uniform.
This is not always true.
Right?
For example, over here you can see that you have three and four which is similar to this, right?
You have three which is less than five over here.
So the left part again is sorted.
But you can see the right part is not sorted.
So we cannot make use of this.
Right.
But this is true if the value at the left index is less than the value at the middle index, then always
the left part is sorted.
And if this is not the case, then always the right part is sorted.
So we will make use of this property to solve this question.
All right so let's proceed.
And again over here let me just call this as the m which is m which is the middle.
All right.
And whatever is left to it is the left part.
And whatever is right to it is the right part.
All right.
Now let's go ahead and write the pseudocode of how we can go ahead and solve this question.
Now first, as we do in the case of the binary search, we will have a left pointer and we will have
a right pointer.
And we will calculate the middle index.
Now we are going to check if the value at the middle index is equal to the target value.
If it is equal, then we can stop because we have found the target value.
All right.
Now if this is not equal then we proceed.
First we have to identify whether the left part or the right part is sorted.
And we have seen that either the left part or the right part in this case will definitely be sorted.
One of these two will definitely be sorted.
So first we are going to identify which part is sorted.
So if the value at the left index is less than the value at the middle index, then we know that the
left part is sorted.
And if that is not the case, we know that the right part is sorted.
So we are going to check this over here.
All right.
And then when we write the code over here we are going to check less than equal to because there will
be a case where the left index and the middle index is going to be pointing at the same place.
Right.
So we still want to proceed in that case.
So over here we are going to check if the value at the left index is less than equal to the value of
the middle index.
If that is the case we know the left part is sorted, else we know that the right part is sorted.
All right.
So that's the step.
That's the first step.
Now let's say the left part is sorted.
If the left part is sorted we are going to decide should I explore the left part or should I eliminate
the left part.
So for this I'm going to check whether the target value is in between the two extremes, which is the
value over here and the value over here.
Because if this is sorted, then this is going to be the least value.
And whatever we have over here has to be greater than anything which we have over here.
Right.
So that is what we're going to check if value at the left part less than equal.
Call to the target value less than value at the middle part.
That means that the target value is in between these two values, right?
So then if that is the case, then we will explore the left part.
That means we are eliminating the right part.
So the whole right part or almost half of the input is eliminated.
Now again we proceed.
If this is not the case right.
If the value is not in between these two, then we can be sure that the target value is not present
over here because this part over here is sorted.
Right.
So in that case we will explore the right part or we are eliminating the left part.
So you can see that we are eliminating half of the input in this case, which is what we are doing in
a algorithm with O of log n time complexity, which is the same thing that we did in the case of binary
search.
All right.
So if the left part is sorted we go ahead in this manner.
Now.
Else that is if the right part is sorted again we are going to check if the value at the middle index
is less than the target value, which is less than or equal to the value at the right index.
So again we are checking if the target value is in between these two values.
If so, then we explore the right part.
That means we are eliminating the left part.
Now, if the target is not in between these two values, then we can just eliminate this part and we
will explore the left part.
So this is how we are doing.
Now let me just repeat once more.
The first step is we are going to check if the value at the middle index is equal to target.
If that is the case, then we can just return right because we have identified the target.
So we can return the middle index.
Now if this is not the case, the second step is to identify whether the left part or the right part
is sorted.
So that's the second step.
Which part is sorted.
Let me just write that over here.
Which part is sorted?
Now, if the left part is sorted, we are going to decide whether we should eliminate the left part
or whether we should explore the left part.
So that is what we're doing over here.
Now if the left part is sorted.
So that's what is happening over here.
If the target value is in between the value at the left index and the value at the right index, that
means the target value is somewhere over here, possibly somewhere over here, if at all present.
In that case, we are going to explore the left part.
That means we are eliminating the right part.
But if the value is not between these two, and because we know that this part over here is sorted,
then we can just eliminate the left part and we explore the right part.
So that is how we proceed.
Right now.
We know continuing to explore means nothing but changing the pointer, right?
For example, if we are exploring the left part, all we are doing is we are going to change right to
middle minus one.
And then we have the left pointer over here and the right pointer over here.
So that is what we mean with explore left part.
Now if you want to explore the right part all we are going to do is we are going to change the left
index to the left pointer to this part over here that is middle plus one.
And then right is still over here.
So that is what we mean with explore right part.
Similarly let's say we find that actually the right part is sorted.
So this means right part is sorted.
Again.
If the right part is sorted we are going to decide should I eliminate the right part or should I explore
the right part.
So that is what we are going to check.
Now we are checking whether target is in between these two values.
If it is in between these two values, we will explore the right part, which is we mean we are going
to change left to middle plus one.
So left is coming over here, right is over here.
And we continue we find the middle again.
We continue with this pseudocode over here or the algorithm.
Now if we see that the target value is not between middle and the value at the right index, then we
are going to eliminate the right part and explore the left part.
So explore the left part means nothing.
But we are going to shift right to middle minus one which is over here.
And then we have left over here.
And we continue with the normal binary search algorithm.
So this is the modified binary search algorithm, which we will use to find whether the target value
is in the array which is given to us.
And we are going to do it at O of log n time complexity, because you can see that at every step we
are eliminating one part, either the left part or the right part.
So this is how we are doing it, right.
So let me just write that over here.
Over here we know that the left part is sorted.
If the left part is sorted and the value is not in the left part, we eliminate the left part.
So you can see we are eliminating the left part right now.
If the value is in the left part, we are eliminating the right part.
So you can see we are eliminating half of the input if the left part is sorted.
Similarly, if the right part is sorted, the value is in between the extremes.
Then we are eliminating the left part or exploring the right part.
And if that is not the case, then we explore the left part and we are eliminating the right part.
All right.
So this is how we proceed.
Now let's walk through the algorithm with an example.
Let's say the target is given to us as three.
And let's say this is the array.
All right.
So you can see that 123456789 is sorted.
So it has been rotated with the pivot five.
So that's why it's looking like this now.
So let's go ahead and write the indices over here.
And our algorithm should identify that three is at index seven.
And it should give back index seven.
So that's the question.
So let's proceed and walk through the algorithm.
So we are going to have two pointers left and right.
So left is pointing to index zero.
And right is pointing to the right most index which is eight.
So we go ahead and calculate the middle index which is floor of zero plus eight by two which is equal
to four.
So we have middle at index four which is over here.
Now we are going to check whether the value at the index middle is equal to the target.
We see that they are not equal right.
So nine is not equal to three.
So we proceed.
So we we we cannot return the index at this point.
Now we are going to check is the left part sorted or is the right part sorted.
So that's the next step.
So for this we are going to compare the value at the left index and the value at the middle index.
We see that five is less than nine.
So therefore we know that the left part is sorted right.
So the left part is sorted.
And you can see that it's actually sorted over here.
So after having established this we have to decide should I explore the left side or should I eliminate
the left side.
For this we are going to check whether target is in between 5 and 9.
So is is that the case.
We see that no it's not the case right.
So target is not between 5 and 9.
So that means target cannot be anywhere over here as well because this part is sorted right.
So we are going to explore the right part and we have eliminated the left part.
So this has been eliminated.
So that's why the time complexity of this solution is going to be o of log n.
Because at every step we are eliminating almost half of the input.
So let's proceed.
So we have eliminated the half right eliminated the left half.
And we proceed.
We are going to explore the right part which means that.
You are going to shift the left index to middle plus one.
So we get this two over here.
So we have the left index over here.
And then we're going to calculate the middle which is left plus right divided by two.
And then we're going to take the floor which is five plus eight by two.
And then flooring it which is equal to six.
Right.
So the middle is going to point at index six which is over here.
Again we're going to check whether the target value is equal to the value at the middle index.
We see they are not equal.
So two is not equal to three.
So we proceed.
All right.
Now again we're going to check and compare the value at the left index and the middle index.
So we have one less than two.
So the left part is sorted.
So we know that the left part is sorted.
Now we have to go and decide should I explore the left part or should I eliminate the left part.
For this we are going to check is this value three in between 1 and 2?
Is one less than equal to three less than two?
Is that true?
No, it's not true.
Right.
So this is not true.
That means we have to explore the right part or we have just eliminated the left part.
So you can see the left part has been eliminated.
And we're going to explore the right part.
That is we're going to move the left pointer to middle plus one.
So half has been eliminated again at this step over here.
So the left is pointing at index seven and the right is pointing at index eight.
Again we go ahead and calculate the middle which is floor of seven plus eight by two which is equal
to seven.
So the middle is going to point at index seven at this point.
And you can see that the value over here is equal to three and the target is equal to three.
So these are equal.
So we have found the target.
And we can just return the index seven.
So we will return seven which is the index which is the middle index at this point.
So this is how we are going to solve this question.
All right.
So you can see it's very much similar to the binary search.
The only thing is we have a few extra operations.
Once we find the middle value again we are going to check is the target equal to the value at the middle
index.
Which is the same thing that we did in the case of binary search.
But if it is not equal, then we have to first check is the left part sorted or is the right part sorted?
Now if the left part is sorted, we are going to check is the value in the range of the left part.
If yes, we will explore the left part.
If no, we will explore the right part and eliminate the left part right.
And then if the right part is sorted, we are again going to check.
The same thing is the target value between the extremes of the right part.
If yes, we will explore the right part.
If no, we will eliminate the right part and explore the left part.
So this is how we are going to solve this question.
And you can see that the time complexity is O of log n.
So we have taken an example.
Let's take one more example just to be more clear.
All right.
So we have taken an example where we always went to the right part right.
So let's take an example over here for example.
Again we have the same array.
And the middle is four.
And let's say that the target is six.
So let's see an example where we move to the left.
So over here we see we have five we have nine.
We know that the left part is sorted.
So five less than or equal to this six over here and less than nine.
So this is true.
So what do we do.
We are just going to explore the left part.
Now this is just going to be binary search now.
Right.
Because we are going to look for a target value in a sorted array.
So this part over here is just sorted.
So this is nothing but binary search right.
So we have eliminated the right part in this case.
And then we move the right index over here.
And then this is nothing but binary search.
So we are just going to check again.
We are going to find the middle value which is zero plus three by two.
And then flooring it.
So we'll get one.
And then the middle value the middle index is pointing at one.
And the value over here is six.
And the target value is also equal to six.
And we have found the index.
So which is nothing but binary search.
So you can see that this logic over here, this algorithm over here which we have just now discussed,
runs in O of log n time complexity.
Because at every step we are eliminating half of the input.
Right.
So that is why this solution or this algorithm runs in O of log n, right.
We are eliminating half at every step.
Now the space complexity again is going to be O of log n if you implement it recursively.
And that's going to be pretty much similar to the implementation of binary search recursively, which
you have discussed.
And the space complexity is going to be O of one if you implement this iteratively.
Now in this section we will implement this iteratively.
So let's go ahead and take a look at how we can code this out.