Hi, everyone.
So today we are going to solve this question so much in our SO today, OK, so let us consider an example.
So this is basically a sword, Tonetti.
OK, so this is basically a of one, two, three, four, five, OK, and what is the meaning of rotation?
So let's say this area is rotated around with three.
OK, so these are two parts of the area.
And I don't suppose this area is rotated around the pivot tree.
Now, after the rotation, this will be my new area, three, four, five, and then one, two.
OK, so this is the example.
Basically, this is the example of a rotated artillery.
OK, so this is an example of what he did today and now what we have to do, so basically we have to
search inside our attitude for today.
Let us consider an example.
So these are three rotated.
So that is and these are the target values.
And we have to find out what index these target values are positioned.
OK, so three so three is present at this index.
So this is basically zero one, two, three, four, five, six and seven.
So this is index seven.
So today is not present inside this area.
So index will be minus one, I answer will be minus one and four zero.
So this is zero one, two, three and four.
So this is present to the respondent at index four.
OK, so the input will basically be adulterants auditory.
So input will basically be out of disordered area and our target value and we have to find the index
at which the target value is present.
OK, and the assumption is basically there are no duplicates, OK, so there are no duplicates inside
the array.
All elements are basically unique elements.
OK, so all the elements are unique.
Now, before starting solving this question, I want to discuss this question one more time.
So in this question, let's see if this question has been modified.
So instead of finding the first and the last occurrence, let's say, I want to find how many times
a human element appeared.
OK, so I have to count the occurrences of an element count occurences of an element.
So here it.
So how many times it is appearing in this area.
So it is appearing two times.
So how many times six is appearing.
So it is not pleasant.
So it is appearing zero times.
OK, so what is the function so that the function will be integer.
Because I have to return the count of occurences.
OK, function will be integer, the input will be a vector in the target value.
Now instead of returning instead of creating understanding of actor since I have to return count.
So what will be our answer.
So I will return.
Last I know the last position, last minus, first plus one.
OK, so the question is count the quantity of an element.
This will be my answer.
Last minus first plus one you can see here.
So the last position is basically for the first portion is basically three.
So four minus three plus one.
So this is basically two and two is our answer.
OK, so I will return last minus first plus one and how to find lost and how to find first that we already
know because we have solved this question.
OK, so I will be able to solve this question and log in time.
OK, so for counting the occurrence of an element inside today.
And so did ready.
So this is the approach.
Find the last element.
Find the first element returned last night as first blessin time complexity will be Logan and the space
complexity will be open.
OK, now, at this point, so first is minus one.
So what?
I will return here.
So basically I will return here.
Zero.
OK, so you can see for six the first and the last boat will be minus one.
So six is not abating.
So at this point I will return zero and add this line.
I will return last minus first plus one.
OK, now let's come back to our current question.
OK, so our current question is basically we have to solve China rotated certain Eddie.
OK, let's see how we can solve this question.
So let us let us draw some diagram.
OK, so we have assorted Eddie.
OK, so foresighted, Eddie.
So this is I saw today.
OK, so this is I saw today.
These are elements that say this is one, this is two and so on.
Let's say this is basically 250.
OK, so this will be the diagram for us.
Ordinary.
OK, now what is the question?
So question is basically this area has been rotated.
OK, let's say this area has been rotated.
So this part will come here and this part will go there.
OK, so what the diagram.
Sodergren will be very simple.
First, this part, so this is this part and then this part.
OK, so basically.
This part, OK, so let's take this elementary, let's say 50.
And this element is led to.
So I have 60 here again, I have 250 here, then the settlement 50.
So I have 50 here and then I have one here.
OK, so this is basically a sorted at.
So this is rotated, so did Eddie.
OK, so in certain areas, so this is my new start point and this is my new end point in this case.
So this is my start point and this is my end point.
OK, so now in this case, this is start and this is and and you can notice here.
So basically start will always be good then end.
OK, so start with bigger than end.
OK.
So basically this will be the situation.
The end point will always be lost in this start point.
OK, if you want, you can draw one diagram.
OK, let us take an example.
Let's take three, four, five, one, two.
OK, so.
Let us draw one more time so that you can understand what will be our diagram look like, and our ETA
is basically our is initially basically one, two, three, four, five.
OK, so for one, two, three, four, five, let's say this is my element, so this is basically one.
This is two, this is three, this is four and this is basically five.
OK, and now this area has been rotated.
So what it will become so it will become three, four, five, one and two.
OK, so this will be deconditioned.
So this is basically three, this is basically four, this is basically five.
This is basically one, and this is basically two.
OK, so in the above example, I did a mistake, so this will be basically one and this will be basically
50.
OK, so I'm sorry.
So this will be one and this is basically increasing.
OK, so this is one side increasing.
And here also the elements are increasing.
OK.
Now, how against all this caution?
So I hope you understood what we'll be able to discuss today so that it is hard that it will look like
this.
So this will be a general diagram for outrated sorted.
So let's say.
This ad is basically increasing order and then.
This one, OK, so this is my start point, this is my end point.
OK, so basically I will apply to buy new search.
So the brute force way for solving this question, what we have to do, we have to find the target value.
So the brute force is basically a linear search.
OK, so for linear search time and space, the time will be linear and space will be open.
But I will solve this question with the help of binary search.
Now let's see how we can solve this question with the help of binary search.
So this is my start point.
This is my end point.
And what I will do, standard approach.
I will find mid.
What made mid will be start by two.
OK, now made can lie here or we can lie here.
OK, so maybe you can lie here.
Made can also lie here.
Now, first case, let's say it is in this part, OK, murders in this part.
So how we can check.
So this is, let's take it, case number one.
OK, so our case number one.
Miles length here.
So how we will check what I will do.
I will simply write if murder is less than end.
OK, so I will simply write.
If mythically.
If it is less than Alef and that means it is lying ahead.
OK, so in this sordid part.
OK, and for lying here, what were the condition for me to be here?
What were the conditions for the conditions to be very simple.
So basically a officemate basically made will be greater than the start.
OK, now let us consider this case.
OK, so here, after we know where the middle is, we have a key value.
So the key can be here or the key can be in the left hand side, so key can be in the right hand side,
key can be in the left hand side.
How do we decide?
So I will separate Tofurky lying in the right hand side, four key lying in the attaches.
So key should be between the middle value and between the end point.
So inside this, if the key basically will be good then made and the key will be basically less than
the end point.
So basically key is lying here at this part in this region.
Then what I will do, I will write start equals murder plus one.
Now, in the early part, what can I do so the MD, so the Ghyslain basically in the left hand side,
so I will right and equals minus one.
OK, so this is our case number one.
Now, let us consider case number two, basically this case.
So this is our case, too, so is lying here.
OK, so it is lying here now again, the key can be lie, the key can be found in the left hand side
or the key can be found in the right hand side.
So for to be present in this part, basically in the left hand side, the key should be greater than
the start and less downward.
OK, so.
If what can I write here, so if the key is a good, then start and basically the key is less than read,
then what will happen?
At this point between the mid and the start, so what can I do?
I will write an article similar to minus one.
And the key will right?
That's the key, will lie in the right hand side of the middle.
So I will right.
So I will write start mid plus one.
OK, and the turkeys.
So the turkeys is basically very simple, basically made equals, equals.
In that case, I will simply return the index, so I will return with.
OK, so I have to handle three cases, case three is very simple to handle.
This is simple binary search and these are two special cases.
OK.
Our first problem is to find where metals lead can lie in this part or it can lie in this part, and
with the help of these conditions, we can find out where it lies.
OK, so one more time.
Let's write this all clearly.
So I'm drawing Bigram one more time, you, Dunklin.
OK, so this is my start point and this is my end point.
OK, so first of all, what I will do, I will find made point, which is Astarte percent right now,
let's say, is Lakehead.
Now to be lie in this part.
So this is basically our let's say this is our case one and this is our case, too.
So in case with with here.
OK, so let us write about the cases like this one, and this is our case, too.
So for me to be laying here, what is the condition?
So basically made should be good, then start and for lying and for gays to murder should be less than
end.
OK, very simple.
Now, now case when the queen can be present in this part or the geek can represent the right hand side.
So for to be presented.
The key should be good, then start and Key should be left handed, OK, so.
If the key is to then start and the key is less than what I will do, so I will write and equals minus
one.
And what I will do, I will write start equals my plus one.
Very simple.
Now, let us consider case number two so she can be present in the right hand side of the world or she
can represent the left hand side of the world.
So what present for you to be present in the right hand side of the world?
What is the condition for key lie between with and.
So I will.
Right.
So if the key is good then made and the key is basically Lieutenant Leonski lies between them lies between
midnight and end.
So I will right start equals my plus one.
And in the early part, it will lie in the left hand side, so I will write and equal to maybe minus
one.
And our third case is very simple, if murder is it close to key, then read, I will write, I will
simply return with.
OK, so now let us write the code if you understood the logic.
So writing code is very straightforward, I will take two pointers, so start will be zero and obviously
the end will be ignored, says minus one.
OK, so again, our standard condition will start as less than articles end.
So what I have to do, first of all, I will find.
OK, so let us find out which is nothing but start plus and try to.
Now, after finding the mud, so the very simple case, so if mud is equal to the given element.
Then I'd have to return, I can simply return.
OK, now let us go to the LS part, OK?
We have to handle two cases, so let us first handle.
This one, OK?
Case one, civil case one, murders basically good, then start OK.
So if aof start.
It's basically.
Than mid.
Sudi A.M..
Now, I have two cases.
So, Jason, I have to check for the key, and so this is case one and the case doing so Ghyslain between
start and OK.
So if.
GI.
It's basically get it and start.
And the key is basically listin.
OK.
Then would have to do so, I have to search in the right hand side so and equals minus one.
In the early part, I can write articles medicalising.
OK, now we will do the similar, so in the elusive condition.
So in the early part.
So it's part means so in the old part, Minsky's Mayday's laying here, OK, ladies, line here.
So I have to these two conditions, OK, the kids between the middle and the end point.
So if the key is.
He's lower than mid.
And the key is basically listin and.
Denki is laying in the right hand side, for starters, plus one.
In the early part, Ghyslain organdy.
Left hand side so and equals to minus one.
OK, and finally.
If this statement if the statement is not being executed, that means the gun element is the gun is
not present inside the area, then I can return minus one.
OK, so let us in our code and then we will try to submit our code.
OK, so.
So we have to read this explanation, OK?
So right, this second condition also.
Now it will work fine.
OK, so let's it.
OK, so our code is working fine, so just remember, you have to use the call operator, OK?
You can try in and take one example to understand it better.
Now of the time and the space complexity, so if you use if you are using linear search, so this is
a very simple approach, time and space.
Now, if you're using Binish search, so the time complexity is basically log often and the space complexity
is basically order of one.
OK, so let us revise.
So the most important thing to understand this question is basically to understand the diagram.
OK, so this will be the diagram.
This is basically the diagram.
OK, so this will be the diagram.
OK, so this is basically the start and this is basically the end.
So start will be good then end.
OK, generally, so this is the diagram for an outdated sort today, and then you have to handle symbols
in both cases, American life here, American life here.
Now, after finding where the mud is lying, you have to find whether you have to call on the left hand
side or do you have to call on the right hand side?
Similarly, you have to call on the left hand side or you have to call on the right hand side.
And that we can decide whether the key is lying here or whether.
So if the key is lying here, then call on the left hand side, otherwise right then side.
So if the key is lying here, then call in the right and say to the race, call in the left hand side.
OK.