Welcome back.
Let's now go ahead and write the function which we just now discussed to search in a rotated sorted
array.
So we can call this function search.
Rotated sorted array.
All right.
Now this function is going to take in the array.
So we can call this numb's and the target value which is target.
All right.
Now you can write this function either iteratively or recursively.
Now we will go ahead and write it iteratively.
Now the recursive function is going to be very same.
Very much similar to the recursive implementation of the binary search which we have already discussed
in a previous video.
So let's go ahead and implement this over here iteratively.
So initially we have left at zero.
So we have these two pointers.
So left is pointing to zero.
And right is going to point at the right most index which is numb's dot length minus one.
All right.
Now we'll just have the initialization of the variable middle.
And then we'll have our while loop, which is very much similar to the iterative implementation of the
binary search.
And this is going to go on looping as long as left is less than equal to right.
And we will either break out of this when this is not true, or inside this when we have identified,
when we have located the target value, we can come out.
All right.
So let's proceed.
Now if left is less than equal to right.
First we will calculate middle.
So middle is going to be math dot floor.
And we have left plus right divided by two.
All right.
So we have the middle index.
Now we are going to check whether target is equal to the value in the array at the middle index.
So if target is equal to numb's at middle.
So if this is the case then we can just return middle and we are out or.
All right.
So this is part of the call of this function.
So we are returning.
And then we'll be out of this function.
Now if this is not equal then we proceed.
So first we have to identify whether the left part or the right part is sorted.
So let's do that.
So if numb's at left if numb's at left is going to be less than or equal to the middle value that is
numb's at middle.
Then we know that the left part is sorted right?
So we know that left is sorted.
Now, if this is not the case, so else we know that right is sorted.
All right.
Now we need to know whether we should look in the left part or the right part.
So for this, we have to see whether the target value is in which range.
So let's proceed.
So let's say left is sorted.
Now in that case we have to check if target is greater than equal to numb's at left.
And.
Target is less than numb's at middle right.
So this means that if this is true then target is in.
That part is in the left part right.
So that means we can explore the left part.
All right.
So what does this mean?
This means left is sorted and target is within the bounds of the left part.
So we can just explore the left part to see whether target is present in the array which is given to
us.
Now if this is not the case.
So if else we know that the left is still sorted, but we also know that target is not in the left part,
so we can just explore the right part.
All right, now, let's proceed.
Now, let's also just go ahead and write the other possibilities.
So over here else means the right is sorted.
Now if the right part is sorted again we're going to check if target is in that range.
So if target is less than equal to numb's.
At.
Right?
Right.
And if target is greater than numb's at middle.
We know that target is in this range, right.
So in that case we can explore the right part.
So again let's repeat what is happening over here.
So we are in this else part.
That means the right part is sorted.
And if this is true then target.
The value of target is in the range of the right part.
So we can explore the right part.
Now if this is an if this is not true, that is the right part is still sorted but target is not in
this range, then we will go ahead and explore the left part.
All right.
So this is how we're going to implement this.
Let's again repeat.
What are we doing.
We are first we are trying to identify whether the left part or the right part is sorted.
Now let's say the left part is sorted.
If that is the case we are going ahead and checking whether target is in the range of the values in
the left part.
If that is true, then we can only find target in the left part.
If that is not true, even though the left part is sorted, but because the target value is not there
in that range, we're going to explore the right part.
So you can see that in either of these cases, we are eliminating half of the input at every step.
And that's why this is a o of log n operation.
Right.
So let's go ahead and complete the function.
So let's say the left part is sorted.
And let's say the target value is in this range.
Then what we what do we do.
We go ahead and explore the left part.
Now exploring the left part means we are going to eliminate the right part, which is making right equal
to middle minus one.
All right.
So this is the same thing what we did in binary search.
If you wanted to only explore explore the left part we did right is equal to middle minus one.
So that's the same thing what we are doing over here.
Now if we are over here if you want to explore the right part again, what what are we going to do.
We're just making left equal to middle plus one.
So this is the same thing that we did in the binary search.
All right.
So let's proceed now over here also the same thing.
We have decided that we have to explore the right part, which means that we will just say left is equal
to middle plus one.
And over here if we want to explore the left part we will say right is equal to middle minus one.
All right.
So that's the end of our function.
Now if we are out of the while loop over here and we have not yet returned anything, then we will just
return minus one, which means that the particular target value is not there in the array which we are
searching.
All right.
So let's go ahead and try to run this function.
And let's test our code first.
So I'm calling the function over here.
Now initially let me just pass in a simple array 12345.
And let's say we are searching for the value one.
So let's try to run our code.
You can see we are getting zero, which is correct.
So one is at index zero.
That's correct.
Now what if I run this with five.
Yes, I get four.
That's correct.
Now let's say that this array has been rotated one time.
So it would be 5123 and four right.
So let's say we are again searching for five.
And we are getting the index zero which is correct.
Let's say we are searching for three.
And we are getting the index three zero, one, two and three.
So this is at three.
So this is also correct.
All right.
So our function is working.
So let's again do one more rotation.
So let's say we have 45123.
And let's say we are searching for again three.
So we are getting four which is correct.
So this is at index four.
Let's say we are searching for four over here and we are getting zero.
That's also correct.
And let's say we are searching for five over here and we're getting index one which is also correct.
So our function is working.
Now let's take this example and let's just walk through the code and see what's happening.
All right.
So we are having this array over here 45123.
And let's say the target value is equal to five.
So let me just write this over here.
So we have 4512 and three.
And the target value is equal to five.
That's what we are searching for.
So let's proceed.
So we call search rotated sorted array function.
And this array over here is passed.
And the target value is equal to five.
Now initially left is going to be equal to zero.
So this is left and right is going to be numb's dot length which is five minus one which is four.
So over here right is going to point at index four.
And then we have middle.
Now zero is less than four.
So that's truthy this while loop over here this condition is truthy.
So we come inside the while loop.
All right.
Now we find the middle value which is zero plus four divided by two which is two.
So middle is pointing to at index two.
Now we are checking whether five is equal to the value at middle which is one.
So that's not the case.
So we proceed.
Now we are going to check whether numb's at left which is this four over here.
Is it less than equal to numb's at middle which is one.
That's not the case.
So we know that the left is not sorted right.
So this is not the case.
So we come to this part and we know that the right is sorted which is the truth.
Right.
So over here you can see the right part over here is sorted.
Right.
So we proceed.
Now because the right is sorted, we come over here and now we are going to check whether target, which
is five, is in this range.
So is target less than equal to numb's at right.
So this is three this is five right.
Five is not less than three right.
So we know that the target value is not in this range.
Now what is it that we know.
We know that the right part is sorted.
We know that.
And we know that target is not in this range.
So we know that target is not in this range by just comparing the two extremes.
Because this part over here is sorted now because target is not in this part, we can eliminate this
part.
That is, we are saying right is equal to middle minus one.
So we are changing this to over here.
The right is at middle minus one.
So we calculate the new middle right.
So over here left is at zero.
Right is at one.
So middle is equal to zero plus one divided by two which is 0.5.
And when we flow rate middle is going to be equal to zero.
Again we check are these two equal.
So we come over here zero is less than one.
So yes that's true.
So we come inside the while loop.
And we are going to calculate middle which is zero.
Now zero.
This this value over here is four and this is five.
So they are not equal.
So we don't go ahead with this.
We come over here.
Now we are checking whether Numb's had left which which is four.
Is it less than or equal to Numb's at middle which is also four.
That's true right.
That's true.
So we know that the left part is sorted.
Right.
And again there's nothing else over here.
So the left also is pointing to the same index where middle is pointing at.
So over here we check whether target is greater than equal to numb's at left.
So we know that five is greater than this four.
So that's truthy and is target less than numb's at middle is five less than four.
That's false.
So we don't go ahead with this.
So we come over here.
That means we're going to explore the right part.
So the right part over here is only this value.
Right.
We just have this one left.
So we're going to say left is equal to middle plus one.
So left is also going to point over here.
And right and left are pointing at the same index.
And then middle is also going to be equal to one right in the next.
In the next loop we have one less than equal to one.
That's true.
So we come inside.
Middle is going to be equal to one plus one divided by two which is one.
And we see that five is equal to the value at index one.
So we are going to return this index which is one.
So that's how our function works.
Now we can see that at every step we are eliminating half of the input.
So that's why the time complexity of this solution is going to be the same as the time complexity of
the binary search which is equal to O of log n, right.
So the time complexity over here is equal to O of log n.
And the space complexity is equal to O of one, because this implementation is the iterative implementation
and we are not using any auxiliary space.
Now again, just to repeat, let's see how we are eliminating the half of the input at every step.
So first we are checking if the target is equal to middle.
So this is the same as the case of the binary search.
Now if that is not the case we have a few extra steps.
We have to first identify whether the left part or the right part is sorted.
Right now, if Numb's had left less than equal to numb's at middle, we know that the left part is sorted,
else we know that the right part is sorted.
So either the left part or the right part is going to be sorted.
Now, if the left part is sorted, we are just going to check the extremities of the left part, which
is numb's at left and numb's at middle.
Now we will check whether target is between these two values.
If that is the case, then we know that target can only be in the left part and we can eliminate the
right part.
So over here we are eliminating the right part.
All right.
Now if the left part is sorted and the target is not in the range of the left part, then we know that
it can only be there in the right part.
So in this case we are going to eliminate the left part.
So you can see that in either case we are eliminating half of the remaining input.
Right.
And in this case if the right is sorted again we are checking if target is in the range of the right
by checking its extremities, which is numb's at right and numb's at middle.
Now if target is in between this, we know that it can only be in the right part.
So we are eliminating the left part right now.
If it is not in this range and the right part is sorted and the value is not in the range of the right
part, we can eliminate the right part.
So we are going to only explore the left part.
So over here we are eliminating the right part.
So you can see that either case, whatever be the case we are going to eliminate half of the input at
every step.
And that's why the time complexity of this solution is O of log n.