Hi everyone, let's do this question.
You are given an integer array Numb's sorted in ascending order with distinct values prior to being
passed to your function.
Numb's is possibly rotated at an unknown pivot index k, where k is between one and numb's dot length
such that the resulting array is this what is given over here where it's zero indexed.
All right.
Now for example, this is the array which is given to you.
And let's say it's rotated at pivot index three.
So 0123.
So this is pivot index all right.
And it becomes 456701 and two.
So this is similar to a previous question we have seen where we have seen that the array is rotated
n number of times right.
Or k number of times.
So if this is the array which is given to you after it is rotated at pivot index three, you get four
over here.
So 456701 comma two.
So this is pretty similar to the previous question.
All right.
So after this array over here is rotated one time this seven over here will come to the first part.
Right.
You will get 701245 and six.
So this is after one rotation.
Similarly after the second rotation you will get six also coming over here.
So that's the same thing that we have seen previously.
So again if you do three rotations you will get this thing over here which is mentioned over here.
And that's the same thing as rotating at pivot index equal to three.
Now given an integer target.
So you are given a target integer.
Return the index of target if it is in the array, else return minus one.
You must write an algorithm with O of log n runtime complexity.
So if this is the array which is given to you, notice that this is a sort.
This is the array 0124567 which is a sorted array.
And then it's rotated one time.
So you get 7012456.
And then let's say for example the target which is given to you is equal to seven.
Now in this case you have to return the index zero because seven over here is at index zero.
Now if the target was ten then you have to return minus one because ten is not present in this array
which is given to you.
And then the catch is that you have to write an algorithm with O of log n runtime complexity.
Now, the naive way of searching for it would be you could just say index off and then you can just
pass this target.
Right.
So index of seven.
So it will give you zero.
So that would be a o of n operation.
Right.
Because in the worst case you will have to go through each of these elements which is a linear search.
But over here it's mentioned that our algorithm has to run in O of log n runtime complexity.
Now again remember the interesting thing to notice over here is first you know that binary search runs
in O of log n runtime.
And then over here also this has something to do with sorting right.
So the array was sorted initially and then it's just that it's rotated a few times.
So again we have to make use of some variation of the binary search algorithm which we discussed to
be able to search for the target value which is given to us in the array, which is possibly rotated
in lo log n complexity time complexity.
So that's the question.
So we have understood the question.
Now let's go ahead and write a few test cases.
And remember in the interview feel free to ask any clarifying questions you have.
So that's very important.
And then once you're done and if you understood the question properly, you can come up with test cases
along with your interviewer.
So you can ask him or her whether it's okay if both of you could come up with test cases together.
So this will cement and ensure that you and the interviewer are on the same page, and that you have
a good understanding of what the expectation is.
So let's go ahead and write a few test cases.
Let's say the array is empty and target for example is ten.
So in this case we cannot find ten in the array.
So we would have to return minus one.
All right.
So that's straightforward.
Now what if the array is 12345.
And you can see it's sorted and no rotations have been made on it.
Now let's say target is equal to three.
In this case we have to return the index over here which is equal to two.
Right.
Because that's the index of this value over here.
Now let's say we have rotated it and we get 3451 and two.
So you can say that this is the equivalent of doing three rotations to the right.
Or it's the equivalent of rotating where the pivot index is this over here right which is two.
So you get 3451 and two.
And let's say the target again is three.
So in this case you have to return zero right.
So over here the target was at index two.
But over here the target is at index zero.
So this is the question.
So we have understood the question properly.
In the next video let's see how we can solve this question with the variation of the binary search.