Hi, everyone.
So today in this video, we are going to solve this question, find a minimum element in our sorted
Eddie.
OK, so consider this example.
So this is sorted, Eddie.
And what is the minimum element?
So the minimum element is one.
So our output will be one.
Consider this example.
So this is our attitude sorted, Eddie, and we have to find the minimum element.
OK, so in this example, zero is the minimum element, so our output will be zero.
OK, so this is our question and assumption is basically.
There are no duplicates element.
OK, so assumption is not obligated elements, are there?
So I have to find the minimum element.
Now let us discuss how we can solve this question.
Now, the first approach, the brute force approach is basically with the help of linear search.
OK, what we will do, we will simply iterate over there and we will find out the minimum element.
OK, so what will be the time and the space complexities all the time will be well and the space will
be open.
OK, but since the search is not considering the fact that given that it is basically a today, I rotated
sorted out.
OK, so we will solve this question with the help of binary search.
OK, we will solve this question with the help of Minnesota.
Now let's see how Minnesota search will help us to solve this question.
OK.
So since the days are rotated, sorted out and.
The result today is the graph of the disorder that is very simple, so it will look something like this.
There are no duplicates, so it will continue to increase and then there will be a sudden drop.
OK, so there will be a sudden drop.
And again, the elements are continuously increasing because there are no duplicates.
OK, so this is New Start Point and this is the end point of the day and we have to find the minimum
element.
So this is basically the minimum element.
OK, we have to find at this point, this is basically the minimum element.
OK, so we have already sold similar kind of question, so again, first of all, what we will do,
we will find out.
OK, so we will find out which will be a start plus.
And why do.
OK, so Gayson.
So for this, the first case, so after finding out the MD, what I will do, so basically this is the
minimum element.
So the next element, this is the next element and this is the previous element.
So both the next and the previous element are greater than the minimum element, obviously.
So after finding out the element, what I will do so the small element should be smaller then the next
element and this element should be smaller than the previous element.
If this is the case, then we have to find then we have already found out our minimum element.
So I will return it because it is the smallest element, so I will return.
OK, so this is very simple example.
Very simple case.
OK, now the second case.
Second guess is this is not true.
OK, so this is not true.
Now I have to find out where my lies.
So suppose it lies here.
OK, what is the condition for me to lie here?
So basically made will be less than and less than articles close to end.
OK, so is lying here.
Now what we have to do if mom is lying here, then we know that the smallest point will be in the left
hand side.
So what I will I will do.
So I will do and equals minus one.
OK, now let us consider turkeys, so in the third turkeys is lying here, OK, so it is lying here.
Is a condition.
So it is basically good.
Then start.
OK, so it is good.
Then start now from the diagram we can see the minimum element will lie in the right hand side.
OK, so what I will do, I will do start equals mid plus one.
OK, so this is very simple.
OK, we have to these three conditions are very, very simple, OK?
Find out the method compared with the next element and the previous element.
Obviously, this has to be the smallest element, which we are going to find out the minimum element.
So if this condition is true, I will simply return it.
If this condition is not true, try to find out where it is laying.
If it lays here, then go in the left hand side.
If my life is here, then go in the right hand side, OK?
So these are the conditions.
So this question is basically present only at court.
And now let us write the cold.
OK, so cold is going to be very, very simple.
OK, so let us see how we can find out the next and the previous.
So what will be next.
So next will we basically made a plus one.
OK, and what is previous.
So previous is basically a minus one.
OK, very simple but there is no confusion here.
OK, so suppose if the value of is end ok.
Suppose if it is basically close to end then what they are doing are trying to find out next.
So what is next.
So next will become and plus one and obviously this is Eddie and the plus one next.
So this index does not exist so you will get married.
You will get around demora now to avoid the entire matter, what I will do so let's say the size of
the error is an OK, so you will you will have to write more than OK.
So and plus one.
Martin, so this is basically and I think this is and normally so and more than this will become zero.
So I will likely reach here.
OK, and similarly with the previous, so you are dealing with a minus one, I suppose, maydays zero,
so zero minus one does not exist, basically minus one does not exist.
So for handling this case, what we have to do, you have to add plus and first.
OK, so minus one plus N what will happen, you will reach an endpoint.
OK, and obviously you have to do more than.
OK, so we are basically jumping so modern, basically, it will help us jump from here to here and
obviously from here to here.
OK, so let me write the code and I will explain it again.
So our goal is very simple.
First, let us change the name to be at a OK, so I have to find the minimum element, so start zero.
And this basically the size, so not size.
So what is the end, so and there's nothing that is just in and minus one.
OK, so now let us write the code, so while it starts listing articles to end.
We will find out and we will find out.
So this is nothing but stark lesson battle and the simple case.
So, OK, so first let us find out next in previous.
OK, let us find out next and previous.
So what is next?
It is nothing it is only one plus one.
OK, so my plus one more than more than is necessary to avoid runtime errors.
OK, so plus one more and.
And similarly, you have to find previous so previous made minus one plus and.
And obviously more than.
So after finding the next the previous, we only have to compare.
OK, so let's compare.
So if.
They made this list in the previous.
And.
It's basically.
Less the next.
So what we have to do, we got our answer, OK, so we will simply return our answer.
And what is our answer?
Our answer is AIFMD.
Simple.
OK, so after this, in the elusive condition.
We have to decide whether we have to move left or right and that we can decide with the help of these
conditions.
OK, so if it is less than articles to end after to and equals minus and so.
If murder is less than end, what I have to do.
I have to move in the left hand side, so Andy calls me to my next one.
In the last part, you can write equals one plus one, OK, or if you want to write the complete condition,
you can also write.
So Elif.
Mud is basically going to then start.
OK, simple enough and finally.
OK, so, yeah, so finally, we will get our answer.
OK, so let's turn our court and then we will try to sum it.
OK, so OK, so.
Let's make it capitally.
OK, so what we have to wait.
We have the right return minus one.
OK, this is why we have to write it down minus one, because the convalescing.
They're babies are in danger, so you have to return something, although this line will never be executed.
OK, so line number 21 will never get executed because we will always have a small element.
We will always have a minimum element.
OK, so but it is necessary for the compilation purpose.
OK.
Now, read some.
OK, so our goal is working fine, so this line is only for completion purposes and this line will never
get executed.
OK, so because we will always have the minimum element, we will always have the smallest element.
OK, so this was a very simple code.
Now let's see one more problem where we can use the similar code.
OK, so the problem is basically.
So you have to find how many times a starter that is rotated.
OK, so basically let's discuss one more problem.
So find out how many times.
Assorted arrays rotated, assorted array is rotated.
OK, so let us solve this problem.
So if you can see here.
Let us consider this example, three, four, five, one, two.
OK, so I have this example, three, four, five, one and two.
So how many times?
Basically this area has been rotated.
So let us consider first a small example.
So let us consider this.
So two, three, five, eight, 11 and 12.
OK, so after one rotation, after one rotation, what will happen?
This will come here.
And this will come here.
OK, so this will be the situation.
Well, two, three, five, eight and 11.
So this is one rotation.
OK, now let's do one more rotation.
OK, so this will come here.
This will come here.
And this will come here.
So it will look something like this.
Then we have two, three, five and eight.
OK, now the question is, so basically this question is question is, you are given this, Eddie.
You are given basically assorted rotated, Eddie, and you have to find how many times this area has
been rotated, so the answer in this case will be to.
OK, this is first rotation and the second rotation.
OK, so this is basically our input and this is basically our output.
OK, so we are doing we have done two rotations to obtain this, Eddie.
OK, so how many rotations have been done to obtain this, Eddie?
So this is very simple.
OK, so the rotation is basically the number of rotation is basically nothing.
It is just number of elements before the minimum element.
OK, so these are the number of rotations.
So a number of rotations are nothing.
It is just a number of elements before the minimum element.
OK, so this is the minor element and how many elements are before the element?
Three.
So in this case, our output will be three.
OK, let's set this example only, so this is the smallest element, so how many elements are before
the smallest element?
Two.
So that's why our answer is to OK, so very simple logic.
OK, so if the question is how many times assorted arrays or.
So what do you have to do?
You have to find how many elements are present before the minimum element, OK?
Or in the other way, what can I do?
What can I say?
The number of rotations is basically nothing.
It is the index of the minimum element index of the minor element because the indexing starts from zero.
OK, you can see.
So this is the minimum element and its index is basically three.
So its index is basically two.
This is zero index.
This is one index and this is two index.
And our answer is basically two.
OK, so since the indexing starts from zero, so what can I do?
So number of rotations are basically nothing.
They are just the index of the minimum element.
So here one.
So what is the index of one.
So zero.
One, two, three, two, three is the index of the minimum element.
So that's why our answer for this input will be three.
As you can see here, three.
OK, so if the question is how many times assorted error is audited, what do you have to do?
You have to just find out the index of the minimum element and how to find out the index of the minimum
element.
So we have already solved this question if we see above.
OK, so if you see about what we are doing here, so what we are doing here, we are finding out the
minimum element.
So instead of finding out the minimum element, I will find out the index of the minimum element.
Basically what we have to do.
So instead of returning.
So if we can see here, if the question is if the question is find out the index.
So instead of returning the minimum element, what I will do.
So what I will do, I will return.
OK, so this is our second question.
Question is how many times a soldier that is rotated?
OK, so if the question is how many times assorted error is rotated, then what do you have to do?
Basically, you have to return mid, you will return them with you will return the index.
OK.
So that's all OK, I'm repeating myself.
So basically this whole code is for solving it, for finding out the minimum element.
OK, so we are finding out the minimum element.
So this is our minimum element.
Now, if the question is how many times assorted errors are treated, then what do you have to do?
You can see here what we are doing.
So what we are doing, our logic is basically saying you just find out the index of the minimum element
and what is the index?
So index is basically nothing.
It is just it.
OK, so this can be the variation of this problem.
OK, so the variation of this problem can be this one.
So the court will be saying everything, the logic and the court, everything will be the same.
So instead of returning, array of you will return unlabelled minus the index of military value.
OK, so I hope you understood this cold, OK, so if you have any doubt in this question, you can ask
me, OK?
So I think we discussed.
OK, so, yes, since we used to buy any such approach in discussion, so the time complexities basically
login, so the time complexities basically go off log in where and is the size of the area and the space
complexities or DRAFFIN.
We are not using any extra space.
OK, so we have discussed the time of the space complexity.
We have discussed one more variation of this problem.
OK, thank you.