Complete BinarySearch Patterns DSA Course(Beginner→Advanced) -Search in Rotated Sorted Array(KumarK)

本站添加: 2026-05-05

[00:00:00]Hi everyone. This is Yashasvi. I'm a third year college student and I recently got Google internship. I did a step internship in this summer which is 2025 but I got a PPI and I'll be returning again in 2026 as a SWE intern at Google.

[00:00:15]>> So hello guys. Welcome. Welcome to our lovely binary search pattern course lecture number two.

[00:00:21]So guys, what happens is that generally these two problems which is the first one is search in a rotated sorted array and then the second problem is find minimum in rotated sorted array.

[00:00:33]There are multiple standard DSA sheets and DSA tutorials teaching these problems but I see there is a core issue with all of them. They are just trying to teach you the algorithm that this is the problem apply this binary search algorithm.

[00:00:47]They are not discussing why is this algorithm only working? Why is there no other algorithm working? What is the intuition? What is the logic? How could you come up with your own self? How could you come up with this algorithm on your own?

[00:01:01]Without any external help. How would you do a normal human based analytical thinking to come up with these algorithms?

[00:01:08]So these things are taught in a very non-intuitive way in other tutorials and videos. So what I will do is rather than teaching in the standard way I will discuss with you what the problem actually is. I will open up the problem in front of you. I will show you some observations.

[00:01:24]And when you see those observations guys, normal human solution would be clear to you. After you know the normal human solution, then I can slowly show you the actual efficient solution which will come out from the normal human solution only.

[00:01:37]So let's start with the procedure. So guys, we are going to solve two problems and both the problems are actually same only. You will come to know about it during the middle of the session. So find you know search in a rotated sorted array. So a sorted array is given to us, right?

[00:01:54]Which is left rotated as written in the question. So if I try to show you the question, let me show it to you in the best possible way.

[00:02:05]Uh there is an integer array nums sorted in ascending order with distinct values.

[00:02:08]Guys, all the values in the array are distinct. They are different.

[00:02:12]Prior to being passed to your function, nums is possibly left rotated at an unknown index.

[00:02:18]So I have to find a number in a sorted array which is very easy to do. I can use binary search if you've watched lecture one.

[00:02:26]But now the array is left rotated. So let me show you what is the meaning of left rotations which are going on.

[00:02:34]So if my array looks like this, let's say my array looks like this, okay?

[00:02:40]My array looks like this.

[00:02:45]We always start everything with the name of God Ram Ram.

[00:02:50]So guys, see my array array looks like this, okay? Zero one, two, three, four, five, six, seven.

[00:02:59]This is a perfectly sorted array in ascending order. No problem. But what is left rotation one?

[00:03:06]Left rotation one means this seven comes ahead by one step. So it would look like seven, zero one two, three, four, five, six. Just a left rotation, okay?

[00:03:22]Then left rotation two.

[00:03:26]It would look like now six will go ahead. So six, seven left rotation three.

[00:03:38]Five would go ahead. Five six, seven, zero, one, two, three, four. Left rotation four.

[00:03:46]It would look like four, five, six, seven, zero, one, two, three. Guys, can you do an observation?

[00:03:55]This is the human way of thinking. You can you see this zero was here then it's going here right right right one step and in the end zero will be here, okay?

[00:04:05]In which left rotation most probably this is left rotation four.

[00:04:09]Then there will be left rotation five, left rotation six, left rotation seven.

[00:04:15]Okay, in left rotation five three will be ahead. In left rotation six two will be ahead. In left rotation seven one will be ahead.

[00:04:21]So in left rotation seven it will be one two, three, four, five, six, seven, zero, okay?

[00:04:30]So guys, left rotation is nothing but what?

[00:04:34]If I pick up left rotation three if I pick up left rotation three, just try to see what is happening.

[00:04:42]The left part is sorted five, six, seven and this right part is also sorted zero, one, two, three, four. So guys, our array has been divided in two sorted parts.

[00:04:55]If this is the sorted array, I will not be always given a sorted array in the input.

[00:05:00]I will either be given L1 in the input or L2, L3, L4, L5, L6, L7. I've not shown L5, L6 because of the space constraint but I hope you know what they are.

[00:05:10]So I will be given a left rotated array.

[00:05:13]So what is a left rotated array? Left rotated array is nothing but left rotated array is nothing but an array created by joining two sorted arrays. That's it. So L3, let's talk about L3.

[00:05:29]L3 only L3, okay? So you know now in L1 this goes at L2, L3, yeah. Five, six, seven, zero, one, two, three, four.

[00:05:41]So guys, when you look at this now only two things should run in your mind.

[00:05:45]This is the left sorted part.

[00:05:49]Left sorted part and this is the right sorted part.

[00:05:54]You see now this thing is actually true, beta.

[00:05:58]Left sorted part and right sorted part.

[00:06:01]So if I try to make the diagram, how does that look like?

[00:06:05]Uh if I try to make the diagram for you five, six, seven. It is increasing like this. Five, six, seven, then it comes down like this.

[00:06:16]Zero, one, two, three, four.

[00:06:19]Like this.

[00:06:21]So it goes up then it goes down, okay?

[00:06:23]It goes down like this.

[00:06:26]So there is this valley valley point.

[00:06:29]So it is like this. Goes up, a valley, then goes up again. So we just have to find the valley point. If you're able to find the valley point guys, this is a normal human way of thinking. See, I did not do anything special. I just showed you that any left rotated array or for the matter you can even call it right rotated array because right rotations will also generate similar kind of arrays, okay?

[00:06:53]So any left rotated array or right rotated array. In the question they have like perfectly said called it as left rotated.

[00:06:59]A rotated array is nothing but an array created of two sorted arrays. Left sorted part and right sorted part. So for left rotation three, five, six, seven is in the left part and zero, one, two, three, four is in the right part.

[00:07:10]So guys, if you know if you know the target value then you just need to check target value is coming under the left part or it is coming under the right part. If it is coming under under the left part, you will just do binary search on this part and you will find out where the target is coming.

[00:07:28]And if the target value is coming in the right part, then do binary search in this range and find out where the target is coming. So it's so easy.

[00:07:39]Let's say L4 is given to you, okay? So it looks like you know like else for L1 seven was there. Six, seven L2, L3 was like this. So L4, okay.

[00:07:52]Fourth left rotation would look like what? Four, five, six, seven, zero, one, two, three, okay?

[00:08:00]Let's say the target value is five.

[00:08:03]You want to binary search and find where is five coming. Very easy. Don't worry.

[00:08:08]It's really easy.

[00:08:10]First step is figure out the left part and right part.

[00:08:15]Figure out the left part and the right part. So left part plus right part.

[00:08:25]So very very easy. You see this is the left part.

[00:08:30]In left part the minimum uh number is four, maximum number is seven.

[00:08:36]In right part minimum number is zero, maximum number is three. Now you only apply common sense. Five. Five is coming in four to seven or zero to three?

[00:08:47]For the left part, you know L1 which is the minimum value of the left part and you know the R1 left part which is the rightmost boundary of the right part.

[00:08:56]L2, R2.

[00:08:58]So you can just write a simple if condition and check is target greater than equal to L1 and less than equal to R1? If our target is greater than equal to L1 and and target is less than equal to R1 then guys, it's simple target is just coming under the left part.

[00:09:15]If target is greater than equal to L2 similarly and less than equal to R2 target is coming under the right part.

[00:09:20]Here our target is coming under the part from four to seven. So now what will I do?

[00:09:27]In step one I figured out that it is coming under the left part. Left part is from four to seven. Now what will I do in steps two?

[00:09:34]Just do binary search.

[00:09:36]Do binary search in the left part.

[00:09:39]This is a common human way of thinking.

[00:09:41]Uh the left whatever array is given to us, we can divide it into two parts.

[00:09:45]Divide in the left part, right part. Now find out your target is coming under the left part or the right part. If it is coming under the left part, left sorted array.

[00:09:53]Now do binary search and find where the number is coming under the left part. If it is coming under right part, do binary search and find out where this number is coming under the right part. That's it.

[00:10:02]So now I will do binary search from 4 to 7. So guys, you know that standard binary search algorithm. 4 5 6 7 is the only array you have. This is the low index. This is the high index. You now can do binary search and find the position of 5 in this. So it will take log n time. So guys, this problem is totally solved.

[00:10:21]Step two is totally clear. Once you know it is the left range, you do binary search in that left range. If you know the target is in right range, do binary search in that right range, L2 to R2 or L1 to R1 if it is in left range. For right range, L2 to R2.

[00:10:32]But guys, L1 step one, there is something which we did not figure out.

[00:10:36]How will you figure out which is the left part and right part?

[00:10:40]Step two is clear to us. We will not discuss about it again.

[00:10:43]But how do we figure out what is the left part and right part?

[00:10:48]You can do it in O of n time, right?

[00:10:50]That is not a big deal.

[00:10:53]You can travel the array from left to right.

[00:10:56]Wherever you see the most minimum element of the array, that is the valley point. See, array looks like this, right?

[00:11:02]It goes up, then it goes down, then it goes up. So this valley point is the breaking point, right?

[00:11:08]This valley point is the breaking point.

[00:11:11]This valley point is nothing but the breaking point.

[00:11:23]How do you find the breaking point? O of n method is very simple. Travel this array and find like this uh these are the indices of the array, right?

[00:11:32]Travel this array and just find out just find out by by by traveling this lovely array just find out uh very simple thing.

[00:11:50]Just find out one lovely thing for me.

[00:11:51]What is that lovely thing?

[00:11:57]Where is minimum element element coming?

[00:12:01]You can travel from left to right in O of n time.

[00:12:03]And index number four is the minimum point. So you know if index four is the minimum point it means everything from four to this is called as the right part and everything before index four is nothing but the left part.

[00:12:17]So guys, can you see everything is happening logical? I did not say any solution.

[00:12:26]So what is actually happening?

[00:12:28]Enjoyment. Lots of enjoyment is happening.

[00:12:32]You travel the array in O of n time. You figure out the breaking valley point, the minimum value.

[00:12:37]Everything from minimum value towards n minus one is the right part and everything before that minimum value is the left sorted part because the array is made in that way. Array is always increasing then a down point then increases. It is always like that, okay?

[00:12:52]So in O of n time you can find the left part and right part and then you can do the step two in O of log n but guys, what is the total time it takes? It takes O of n plus log n time. Which is not very efficient because you're traveling the whole array at least one time. Now can you optimize the step one to O of log n?

[00:13:12]Can you optimize the step one to O of log n?

[00:13:21]Can you optimize the step one to O of log n? Yes, you can.

[00:13:25]You are now trying to find the minimum element of this thing, okay? You're trying to find the minimum element of this left rotated array or you can call it as right rotated array. In the end I will show you left rotated array. If there is a left rotated array, it can also be generated by some number of right rotations as well. So nothing to fear about.

[00:13:44]So how can you find the valley point by doing binary search? Now this is really complicated.

[00:13:51]Yes, it is.

[00:13:53]So how to do that? Let's think about it.

[00:13:57]Let's take a bigger rotation, right?

[00:13:59]Let's take a Let's take L6. Yeah, L6. Let's take L6.

[00:14:09]4 5 so 2 3 4 5 6 7 0 1 2, okay?

[00:14:16]So this is a left rotation. There were many left rotations in the example as well.

[00:14:20]If I try to show you yeah.

[00:14:24]4 5 6 7 0 1 2, okay? Yeah, so let's go.

[00:14:28]So guys, Ram Ram.

[00:14:30]Now this is L6. You have to find the minimum element.

[00:14:35]You have to find which is the minimum element. You have to find its index also.

[00:14:39]We know what is its index. We can see that because we have eyes but how will the algorithm find out?

[00:14:44]We know that the answer is six. How to find it out? Do binary search.

[00:14:50]Left value right value.

[00:14:54]Okay, guys?

[00:14:56]L is pointing here.

[00:15:00]R is pointing here.

[00:15:04]Complete full focus full focus.

[00:15:07]L is pointing to zero. R is pointing to eight. What is the mid value? You know how you calculate mid?

[00:15:13]So 0 plus 8 by 2 4. So this is the mid value.

[00:15:19]Our target is the minimum element. The mid value is what? Let's see what is the mid value.

[00:15:25]Mid value is six. Mid value is six.

[00:15:30]Directly compare six with the last element.

[00:15:37]You got your mid value as six. Compare six with the last value.

[00:15:42]If six was less than equal to two if six was less than equal to two it means six is in the right part.

[00:15:53]But six is not less than equal to two.

[00:15:57]If your middle part which you currently are at, if it is bigger than this it means six is in the left part. Six is in the left part. Six is in the left part. Six is in which part?

[00:16:13]Left part. Okay? So you're trying to find the pivot. You're trying to find the value, okay? So I can show it to you with multiple examples, okay?

[00:16:21]For example let's say instead of six your mid was one. Your mid was what?

[00:16:29]Let's say your mid was hypothetically this guy.

[00:16:32]One.

[00:16:33]Okay?

[00:16:34]Now compare this one with this last value. One is less than equal to two. If your current value is less than equal to two, it means your one is in the right part. One is in the right sorted part.

[00:16:43]If the current value is less than equal to last value, it means current value till the last value is in sorted direction. Is it in sorted way? It is the right part. It is the right part.

[00:16:52]This is the biggest observation which solves the whole problem whenever you are at a mid value.

[00:16:57]Compare that mid value with the last value.

[00:17:00]If that last value if that last value is less than equal to the current value. If that last value is less than equal to our mid value, it means everything from here till the end was sorted.

[00:17:16]It means we are in the right part. We are in the right part. But if that mid value is not like it is not greater than this if that mid value is not greater than us it means we are in the left part and that is the right part.

[00:17:32]So for six, what happens?

[00:17:35]You see that six is greater than two.

[00:17:38]It means six is in which part? Six is in left part.

[00:17:43]Six is in left part.

[00:17:45]So six is in left part. The only deduction you can do by this mid is that six is in the left part. Six is in the left part. Six is in the left part. Now the things are very easy.

[00:17:58]We know that the minimum number will always be in the right part.

[00:18:02]So six is in the left part. Six is in the left part. Six is in the left part.

[00:18:07]Six is in the left part. So the minimum will be where? On the right hand side.

[00:18:13]Six is in the left part. So now how will I update my L? Earlier my L was what?

[00:18:18]Zero.

[00:18:19]Now my L will be mid plus one.

[00:18:23]Earlier my L was pointing to zero. Now my L will point to this guy. So now I will be searching in this range, 7 0 1 2. Why?

[00:18:33]I know my current guy. I know my current guy is in the left part.

[00:18:37]It means the minimum zero guy must be on the right part. And for right part, I need to go in the right hand side.

[00:18:43]That's why L equal to mid plus one.

[00:18:55]Also one more thing you should always keep check of while trying to find the pivot, okay? Which is very very important.

[00:19:07]This left right thing I am sure it is getting clear to you guys, okay?

[00:19:11]Like uh let's take some like before I take some other example if you directly hit a mid as this now, always be very careful, okay? You are hitting let's say mid directly to zero, okay? Okay.

[00:19:26]Any other number you check now, they will always be like this.

[00:19:33]The mid minus one value will always be strictly less than mid and the mid value will always be strictly less than mid plus one.

[00:19:42]This is true for all the values all the values except seven and zero.

[00:19:52]Because when you are at zero, it looks like this.

[00:19:57]You are mid, so you have to add a check condition.

[00:20:00]If the left value is also bigger than you, if mid minus one is also bigger than you, and mid plus one is also bigger than you. You can see here zero, mid minus one seven is bigger, and mid plus one one is also bigger. Then you are indeed the minimum value because this valley thing can happen only one time.

[00:20:18]And special condition for this seven also.

[00:20:22]If the left hand value, this is mid, left guy is small or left guy does not exist, that's okay.

[00:20:31]But if the right hand side guy is smaller than you, it means you are a peak.

[00:20:37]So you can just declare yeah, seven is the peak. It means zero must be on the right hand side of seven.

[00:20:42]So guys, apart from the conditions I told you now, you should How will you know whether your current guy is the right guy or not? How will you know that?

[00:20:51]To know whether the current guy is the right guy or not, what you can do is you can check these things. By checking these things you can come to know is your number seven or is your number zero. If your number is seven, if your number is indeed seven, then just go one side on the right hand side and the job is done.

[00:21:10]Okay? And we will never be doing this algorithm on this this type of array.

[00:21:16]0 1 2 3 4 5 6 7 We will never be doing here. Why?

[00:21:21]Because we can state in the start only that A of zero is less than equal to A of seven. It means it is already sorted. So you can just do a normal binary search in this full range from L to R. Okay?

[00:21:32]So whenever there is a seven, there will be one space on the right hand side. So if you hit a seven, this is the answer.

[00:21:38]If you hit a zero, you know that zero condition, it always look like this.

[00:21:41]Left guy bigger than you, right guy also bigger than you.

[00:21:47]Okay, and we are at the mid. Okay?

[00:21:49]This much is clear to you people.

[00:21:52]So guys, that's it. What is the algorithm? Algorithm is pretty simple.

[00:21:56]As soon as you get a midpoint, check is it the is mid minus one mid plus one greater than us?

[00:22:01]Then yes, that's our answer.

[00:22:03]Is mid plus one less than me?

[00:22:05]Then that guy is the answer. And if none of them is happening, it means it means this is mid, this is mid minus one generally, and this is mid plus one. So I am a part of I am a part of what? I am a part of sorted array. So I should figure out whether I'm in the left sorted array or I'm in the right sorted array.

[00:22:26]If I'm in the left sorted array, I will try to move my pointer to right.

[00:22:30]And if in my right sorted array, if I'm in the right sorted array, so let's say my number is let's say three.

[00:22:42]Okay?

[00:22:43]And this is four, and this is two.

[00:22:46]And this is my mid, and I know that this thing is in the right sorted array.

[00:22:52]So obviously I will try to go to left because the minimum value zero or minimum will be on the left hand side, right? But if I'm in the left sorted array, I will try to go to the right hand side.

[00:23:02]Like if I want to show, I can show you example like this. 5 6 7 0 1 2 3 4.

[00:23:07]Okay?

[00:23:08]Let's say somehow my mid is coming here.

[00:23:13]So my mid is coming here three. I will do what? I will check. First of all, I will check yes, this is a part of a sorted array because it is going like this. And three is less than equal to four. Three is less than equal to four.

[00:23:24]It means three is in right sorted array. If three was not less than equal to four, three was would be in left. This is right.

[00:23:30]So this is my mid. Okay?

[00:23:34]Then what will be let's say this was my L. It could It cannot be your L, but still let's just take example L R and this was the mid.

[00:23:42]So this is the mid. You know that the answer is on the left hand side. So what will you do? You will declare your R as mid minus one, and now you will search in this range 7 0 1 2.

[00:23:51]For this L and this R, this could not be the mid. I'm just taking an example.

[00:23:55]Okay?

[00:23:56]So guys, now let's go through the C++ Java and Python codes. Uh like that What the What is the What are the total number of operations? It is O of two log n because we are doing step one to find the minimum element. Once we know the minimum element, guys, we know the left part, we know the right part, we can check target is in the left part or right part, and we can do binary search in that part in again log n time for step two. And in two log n time it is getting done, and two is a constant, so you can say that it is log n complexity.

[00:24:22]This is the human way of doing. Now that you know the human way of doing, now we can go towards the optimized approach where we don't have to run two binary searches. Now first, let's check the code of the two binary searches. It's lovely and very very cute. So let's do that. Ram Ram.

[00:24:40]Seems I need lots of water and hydration today. Anyways, now.

[00:24:45]Guys, you can see the possible rotations I tried to make here zero.

[00:24:48]1 2 3 4 5 6 7. Here the zero is going on the left hand side.

[00:24:52]Okay, see guys, there are multiple ways.

[00:24:54]In the video I showed you this seven gone front, six seven gone front, and things like that.

[00:24:59]Okay?

[00:25:01]So it's possible like the I am trying to these I would call them as right rotations. Okay?

[00:25:08]Uh or wait wait wait. 0 1 2 3 4 5 6 7. I took this and I put it there. Okay, so that was left rotation.

[00:25:16]Yeah, this I can call it as right rotations. Okay, but so it does not matter left rotation or right rotation, you get the idea.

[00:25:23]No matter what type of rotations I show you, they are just made it off made up of two sorted arrays. First part, second part.

[00:25:29]Left part, right part. Left part, right part. Left part, right part. So you can read all this material, try to understand it in best way possible. Now. So guys, we have already solved the second problem.

[00:25:39]Second problem was what?

[00:25:41]Second problem we can just solve in step one now, log n time. Find the minimum in rotated sorted array, the pivot element that we do in step one, and in step two we find that target element because we know the left part and right part, right? So find minimum in rotated sorted array, this problem has already been solved. Okay? You can see such a nice thing it is, this problem uh has already been solved.

[00:26:02]Okay?

[00:26:04]So guys, now let's check the C++ Java and Python codes for search in rotated array. Okay?

[00:26:10]So here we are in two binary searches. Let's check the C++ code, and then let's think think how we can do it in just one iteration.

[00:26:18]Okay?

[00:26:19]Then there are some follow-ups which are asked in Amazon SD internship interview.

[00:26:23]We will go through them also. Okay, we will go through them also. Okay?

[00:26:28]So first, let's go through the C++ code.

[00:26:30]Okay?

[00:26:38]So hopefully things become visible here.

[00:26:41]Like uh copy to code editor. Okay. So guys, see what is happening in the C++ code.

[00:26:46]If n is equal to one, guys, I just directly return that element in A of zero, right? Without any stress. Okay?

[00:26:52]If n equal to two, I just check the two elements. If any is target, just do that because these are very small ranges, and I you should not do too much calculation in those small ranges. If you want, you can, but it can get complicated. Okay?

[00:27:04]Now guys, I'm trying to find that valley point. Low is zero, high is this. Valley is minus one. L1 R1 for the left sorted range, which I will try to find. L2 R2 right sorted range. If A of low is less than equal to A of high, it means the full array is already sorted. So L1 the only one range one sorted range is there in that case. So L1 low, R1 high. L2 R2 does not exist.

[00:27:26]But if this is not the case, it means there are two sorted arrays for sure.

[00:27:30]So in this else case, it means two sorted arrays exist for sure. Okay?

[00:27:37]Okay, clear.

[00:27:39]So guys, yeah, I will go through low and mid. Okay, now I'm checking. I'm checking some things. So mid minus one should be greater than equal to zero.

[00:27:47]And if my mid minus one is greater than me, okay. So if this is mid, and mid minus one is bigger, so it means this is the valley point here, right? So this is the smaller point. We found our valley.

[00:28:01]So this is our valley point. Okay? But if that is not happening, then uh this is the mid, this is the mid plus one. Okay? So if I am bigger, I am okay.

[00:28:14]Okay, so I am bigger than mid plus one.

[00:28:17]It means it is the peak point. Mid plus one is the valley in that case. I Basically I am seven and this is zero, so yeah.

[00:28:24]But if none of those cases are happening, then then it's very very easy. Those cases I covered. Now.

[00:28:30]Now it is sure that it is See, this case is not happening, and this case is also not happening. It means it is this this this. We are in a sorted array. So just check with the last element.

[00:28:40]If our current element is less than equal to last element, it means we are in right sorted array. If you're in right sorted array, it means you need to go to left. So that's why high equal to mid minus one. But if it is not, it means we are in the left sorted array. We need to go to the right. So low equal to mid plus one. Done.

[00:28:57]Done. Valley found out. So L1 will be zero.

[00:29:01]R1 will be valley minus one. R2 L2 will be valley, and then R2 will be n minus one. So left part, right part figured out. This is the left part.

[00:29:08]This is the right part. Now just check now your target is where.

[00:29:11]So if target is greater than equal to A of L1 and less than equal to A of R1, then L1 R1 is the range in which we have to find the target.

[00:29:18]Or if target is greater than equal to A of L2 and less than equal to A of R2, then L2 R2 is the point where we have to find it, right?

[00:29:25]If L equal to minus one, it means something happened and we could not find anything, so minus one. Okay, when that case occurs, we don't need to think much about that.

[00:29:32]Now guys, just do a simple binary search in your correct L R range and find the number L plus R. If this is target, this. If A of mid greater than target, R equal to mid minus one. You know that thing, right? That L equal to mid plus one. You You know these basic things. You're very smart for that.

[00:29:47]And guys, that's it. Now let's check the Java and Python codes which are very much similar, okay? Ram Ram.

[00:29:53]So Java code and Python code.

[00:29:59]Then let's think how can we do it in just one iteration, okay?

[00:30:04]So guys Java code is very much similar like you don't need to worry. Everything is same, okay? See n equal to one case, n equal to two case, low, high, value L1, R1, R2, while conditions, all the things are exactly the same. Like the syntax of C++ Java is so same there is literally no difference, okay?

[00:30:27]You can just check it out. And yeah, this fire emoji, sorry for that.

[00:30:32]Uh now let's check the Python code.

[00:30:34]Python code is also very simple like L1, R1, L2, R2. See the basic computations in C++ Java Python the codes are very similar when you're just writing while and if else it's just the same.

[00:30:44]Like even a Python guy can understand the C++ guy code, okay?

[00:30:48]Yes, in binary search questions the C++ guy can understand Python guy codes and Python guy can understand Java and C++ codes. So you can see n equal to n equal to one, n equal to two case.

[00:30:58]This those can be omitted. If someone is able to omit them, let me know in the comments. We will update that, okay?

[00:31:04]So L1, R1, L2, R2 you understood. A of low this thing you know, this thing you know, right? Mid minus one conditions and all.

[00:31:11]L1, R1, L2, R2 and that's it, okay? Now how to do it in just one binary search. And if you do it in one binary search guys now it will become O of log n, okay?

[00:31:24]Follow-ups were asked in Amazon SD internship interview. Before we go to the follow-ups, think about how can you do it in just one binary search.

[00:31:33]Okay.

[00:31:35]We are trying to find some element, right?

[00:31:39]So let's try out. Let's see what happens actually.

[00:31:46]Okay, so let's take some left sorted rotated sorted array and right rotated sorted array, okay?

[00:31:50]So let's say it is 5 6 7 0 1 2 3 4, okay?

[00:31:56]Let's say the target element is three.

[00:31:59]You are trying to find three. Where is three, okay? So what you will do? This is your low.

[00:32:05]This is your high.

[00:32:07]Okay?

[00:32:09]What is your mid?

[00:32:11]My mid will be 0 1 2 3 4. This.

[00:32:18]First thing which I can do is I can check whether this part is in the left part or the right part. So directly check one with four, no?

[00:32:26]Okay, I checked one with four.

[00:32:28]One is less than equal to four. One is in the left part. One is One is in the left part without figuring out the pivot. I just know that one is in the left part.

[00:32:38]I just know one is in the left part. One is in what? Left part?

[00:32:42]I don't know this point, but I do know that the end point is n minus one. I know one is in the left part. One is in the left part. So I do know that everything from one to four is in what?

[00:32:53]Left part. So I will just check target is target coming in this range or not?

[00:32:59]Yes, target is coming in this range.

[00:33:02]So I just need to do binary search in this range.

[00:33:06]And now my low should be because target is coming in 1 to 4. Three is coming in 1 to 4. Low should go one point ahead and low should point to two.

[00:33:14]So low should just become mid plus one.

[00:33:17]So guys, problem solved. My god.

[00:33:20]When you are at mid, just check are you in the left part? Are you in the left part? Are you in the left part?

[00:33:27]Yes.

[00:33:28]I know everything from now till the end.

[00:33:31]I know it has been ingrained in the brain. Is in the left part.

[00:33:33]Is the target is also in this part? Yes.

[00:33:38]Low equal to mid plus one. Search in that range. Now let's think what would happen if target was zero, let's say.

[00:33:55]In that case what would you do?

[00:34:00]This is again low. This is again high.

[00:34:03]This is your mid.

[00:34:06]You know one thing.

[00:34:07]You know that we are in the left part now.

[00:34:12]You know we are in the left part.

[00:34:14]And you know that this is the right part, okay?

[00:34:16]You know this one is in the left part.

[00:34:19]You know there is this four in the left part. And you know that this right part starts here and these numbers are bigger than four. You know that. This is the left part. And the left part you don't know the starting number, but you know the last number is as big as four. And here in the right part all the numbers are greater than four. All the numbers are greater than four because left sorted, no?

[00:34:39]You want a number zero which is less than my current number.

[00:34:45]You want a number which is less than my current number. It means it could only be on the left hand side.

[00:34:50]So now I will update my high to mid minus one because it could only be in the left hand side. So my high will be updated to this zero. So I will be searching in 5 6 7 0.

[00:35:04]Why?

[00:35:05]Earlier I was searching from this was the low, this was the high.

[00:35:09]Now I know I'm in the left part.

[00:35:12]And I also know that I want a number smaller than this. So it means the target number is Sorry, I know that I'm in the right part. Sorry, yeah. We call it as the right part. I If I called it as the as the left part in the video back, don't get get confused.

[00:35:27]I know I'm in the right part. I know I'm in the right part, okay? Right sorted part.

[00:35:33]If the number is coming in this range, go in that range towards the right hand side and search it out.

[00:35:39]But if the number is lesser than this, but it is still in our range only.

[00:35:42]It is surely in our range because the left part is having all numbers greater than four. And we want a number less than one.

[00:35:48]So go on the left hand side and update your high as mid minus one. So it will be searching from 5 6 7 0, okay?

[00:35:55]Now what would happen if What would happen if Now it's interesting.

[00:36:01]If target was five.

[00:36:10]This would be low.

[00:36:12]This would be high.

[00:36:14]And this would be mid. You know that yeah one is in the left hand side part. You can just check this, no? Yeah, it is in the left hand side part. Okay, great man.

[00:36:26]So you know that everything from one to four is in the Sorry, this is called as a right sorted part. This is called as the right sorted part. You know that one to four is in the right sorted part. You know that the four is the largest number here, okay? Okay, sir.

[00:36:40]But you see target is even bigger than four. It means target comes under left part.

[00:36:47]For the right part the largest number is four.

[00:36:51]And you want a guy bigger than that. It means that guy is on the left part. It means you should search on the left part.

[00:36:57]So I will again update my high as mid minus one and I will search for 5 6 7 0 here, okay?

[00:37:02]Now let's take another case where my Let's say my low was this.

[00:37:09]Okay? My high was this.

[00:37:12]And my mid was seven.

[00:37:14]Okay? So how would you know that this is First of all you would check seven less than equal to four. No, it means it is on the right hand side.

[00:37:21]It is on the right hand side. Now you would check what are you searching.

[00:37:24]Let's say your target was Let's say it was six.

[00:37:28]So you know this is five. You know that five to seven You You know that this current number and this guy are coming under left sorted part. And they are bigger, you know that also.

[00:37:37]If this six is coming under this range, you will just do binary search here. So your high will be now mid minus one. And instead of five to Instead of five to one you will search in five to six, okay?

[00:37:46]This will become m minus one, right?

[00:37:48]But if your target was let's say zero, it like you know that this is in the right hand side part now. So you know that zero is not in our part possible because our smallest value is five. And our current value is seven. So we are in the left sorted part. We don't know how much it is, but five is the smallest number and we want even smaller than that. It means we need to go to the right sorted part.

[00:38:08]So my mid would extend to uh you know?

[00:38:14]Sorry, high would become mid plus one and we would be searching in this range zero to one for that. So like this you can always make if else conditions and the job is done, guys. So lovely we did it in just one binary search iteration.

[00:38:25]So let's check now the codes.

[00:38:27]So guys, uh the follow-up questions are very easy, okay? They were asked in Amazon SD internship interview.

[00:38:34]So I tried to include the recent company interview questions also so that my students are fully prepared and then they can can crack the highest value, you know? Um offers.

[00:38:45]So C++ code.

[00:38:50]Okay?

[00:38:52]So guys, now in a very lovely manner let's check the C++ code, okay?

[00:38:57]So guys, for the C++ code you can see low, high, right?

[00:39:00]>> [laughter] >> If you found the value be very happy.

[00:39:04]Else just check whether you're in the right part or you're in the left part.

[00:39:08]If current is less than equal to this, we are in the right part.

[00:39:12]Or we are in the left part. If you're in the right part, simple condition, guys.

[00:39:16]If you're in the right part, if your target is also less than equal to that, then you can just apply normal binary search conditions.

[00:39:22]Because target is less than equal to a n minus one means target is in that part only.

[00:39:27]So if current less than target this, current greater than target this. Normal binary search things, okay?

[00:39:33]But if target is out of this range, it means you need to go to left sorted part means high equal to mid minus one. You go towards the left.

[00:39:42]And guys, if you're in the left sorted part, if your target is greater than equal to the first element of the left part, it means your target is in the left part only. You can now apply normal binary search there.

[00:39:53]If current less than target this, if current this this this, okay? But, if current if target is lesser than five also, it means target is in the right part. So, you need to go towards the right low equal to mid plus one.

[00:40:05]Such a nice lovely algorithm, my goodness. So, C++ Java Python codes are very similar.

[00:40:09]So, I'm not showing you the Java and Python codes. You can go through the Java and Python codes of the same thing, okay? Here, the links are this document and everything will be provided. Search in rotated sorry sorted array 33 and find minimum in rotated sorted array 153. Both have been taught here.

[00:40:23]Now, guys, how many times the array was rotated? If this question is asked to you in Amazon SD internship interview, what you will say? You will just ask them what is the definition of left rotated sorted array or right rotated sorted array.

[00:40:36]Is it taking the element from here and putting it towards the left?

[00:40:40]So, in that case, uh you can easily find out how many times it is left rotated.

[00:40:44]Know the pivot position. The pivot position is nothing but the number of times it was left rotated.

[00:40:50]Kth smallest element also very simple.

[00:40:51]If you know the pivot position, from zero till that, you know there are how many elements. So, you can figure out how many to where will be the Kth element. All these are homework for you.

[00:41:00]How to find how many times the array was rotated, let's say left rotated or right rotated. First, ask the definition to the interviewer.

[00:41:06]Then, with the help of pivot element, you can tell how many times the array was rotated. How to find the Kth smallest element homework? Write the answers of this with the timestamp in the comments to look let me know that you were able to reach till here.

[00:41:17]What if there were duplicates?

[00:41:19]The average case solution would be O of log n, but the worst case can go to O of n, which we will discuss in the upcoming next video. Hopefully, you guys like this video. Ram Ram.

[00:41:29]Ram Ram.