BS-4. Search Element in Rotated Sorted Array - I

hey everyone come back to the channel I hope you guys are doing extremely well so we will be continuing with our binary search series which is the part of the Strivers A to Z DSi course just in case you haven't checked it out yet there's a link in the description I'll highly

recommend you to check it out so till now I've covered up till this particular problem now in this video I'll be covering up the problem search in a rotated sorted array so what does the

problem state it states that you have to search in a rotated sorted array now what is the definition of rotated sorted array let's understand imagine I give

you an array like one two three four five now this is a sorted array now I ask you can you rotate it at this point so what you'll do is you basically take

this four five and you'll rotate it to the front and this one will move ahead so this is what will be the rotated sorted array so basically just uh stand

one stand at one element and take it to the front and then you shift it so this is the definition of a rotated sorted array so if you look at this particular

example over here you can see that this is the array and then you can just go over like this so it's like one two three four five six seven eight nine but it has been rotated at seven that is why

789 is at the front and then you have one two three four five six now your task is to find out the target so if I ask you where is the Target it is at the index 3 that is what you have to tell me

now there's one other thing this entire array will just have unique elements now this is the first part of the problem we will be solving for Unique elements and the next part we will be solving for

duplicates as well so this problem comes up in an interview what is the first solution that comes to your brain definitely linear search could be like I'll iterate through the entire array

I'll check element by element and the moment it gets compared with the target I return the index 3 and the worst case scenario will be if the target is given

as 6 I end up going to the last element and that is where I found it out so big of n will be the time complexity if I go through the linear search approach

I'm not going to write it down if you want the code you can find it in the notes so a very simple linear search will find me out the occurrence of Target but over here it's clearly stated

search it's stated rotate it or rather sorted search and sort it whenever you hear about these two terms what comes to your brain obviously binary search

obviously binary search comes to your brain now in an interview the interviewer might not give you a hint about binary search so it's better to just tell him that I'm

thinking of a big of n solution but I know there is sorted that is why I have to think of my research you have to tell them in this way you cannot say okay this this problem will be solved by binary research if you tell him why are

you thinking of binary search and the answer is because we have to search and there's a property as sorted and whenever it is sorted we can eliminate portions we can just

go from a n size array to n by two size then to n by 4 size this is what happens in binary search you either eliminate the left half or the right half so let's

for a moment pause on this particular problem and go back to our binary search thing so if you remember in a binary search if you have one two three four five

and you have a target of one or if you have a target of 5 so what what you did was you took a

lower at the zeroth index and it took a higher the last index and then and then you figured out the mid so what did you do at the first step you took three and you compared with the target it's not

equal and then what you did was you like three Target one is lesser than three so I'm very much sure that the right element will be eliminate uh sorry the right half will be eliminated as

very much short why because the entire array was sorted and I'm very sure everything on the right will be greater than 3 will be greater than three thereby Target one cannot exist on the right

fair enough similarly I just checked for five and I was like five greater than lesser than three no so I'm sure that the left half will be eliminated and 5 will be on the

right so just checking on one half very critical point just checking on one half made us sure just checking on

one half was okay like if I just check if one is lesser than three I know it always lies on the left if I just check five lesser than

three I not realize on the right just one half of the checking was okay so this is what we did in binary search keep this in mind that if we check for

one half I was very sure where my target will be will that work over here let's analyze let's go the standard binary search way so I'll just write down the indexes for

easing it out and we know initially low will be pointing here and I will be pointing here where does mid start with the mid starts

from here which is basically 0 Plus 8 by 2 so that's four so the mid stands at the fourth index what is the value at the fourth index too is that equal to the Target no it

isn't so we haven't found out our element what's the next step of binary search it kind of eliminates one half very important to note this down it kind

of eliminates one half now this one half can either be left or can either be right now you're not sure about which have to eliminate

so it can either be the left half or it can either be the right half so if you're standing at two now can you surely say one thing if one is lesser than 2

then can you surely say that it will lie on the left hand side can you surely see it over here that is true because one is on the left over here that is true if one is on the left

so ideally according to that logic if I just remove this and for for a moment I just change it to eight in that case can

I say since 8 lesser than 2 is false because your mid element was 2 and this is false so I can surely say that it will never lie on the left top and it will always

be on the right half according to binary search but that is false why because over here the left half might not be completely sorted which is the case over here so

there is eight because the left half is not completely sorted so you just cannot check on one half that is the key point over here just cannot check on one half and be very sure that it will lie on the

right half that works in binary search because the left half and the right half both are sorted in this case if you do some observations

the left half is not sorted and the right half is sorted observation the left half is sorted sorry the left half is not sorted and

the right half is sorted so first keep point over here is please identify you have to identify I identify the

sorted half that is the key point over here go ahead and identify the sorted half is it the left half or is it the right half

once you have identified then you can perform a check so let's identify so if you're standing at two how do you recognize that the laptop is

not sorted it's very easy because the lower value is not smaller than 2 because we have unique numbers the low value should ideally be smaller than 2

which is not the case thereby the right half is something which is sorted for sure I know that the right half is sorted for sure this is where I'll say

Okay since I know the right half is sorted I can do a check for one I'm like hey one are you between 2 and between 6 why do I see this because all the

elements will be between 2 and 6 in this portion because it is sorted are you there he says no blue I'm not there I'm like okay fine in that case I'll

eliminate I'll eliminate this half I can surely eliminate this half it was not equal to this and now the right half is eliminated thereby the high goes here

perfect so the high goes to one let's again find out the mid will be the mid it'll be 0 plus 3 by 2 1.5 which is an integer value of 1 there by the mid

is this let's write this again what's the first thing you cannot straight away go and check out first thing though obviously you'll check with this and that's not the case the first thing always check with mid the same

thing you did in my research I have to eliminate you have to eliminate that's the next step eliminate either left or right but you don't know where to check so you'll be like this is my left half

and this is my right half what's the step identify the sorted up because unless until you identify you cannot straight away check some like seven eight are you sorted he says yes I'm

sorted how did you recognize because this element at low and this element at Mid where following the property of sorted where following the property of sorted thereby they are sorted

if I look at the right half they're not following the property of sorted ideally for the sorted property to being followed one should have been greater than 8 which is not the case which is

not the case thereby I can safely assume the right half is not sorted and the left half is sorted I can right

so thereby the left half is sorted hence you check are you there on the left are you there on the left he's like aha no if I was there then I would have eliminated the writer but I'm not there

so please eliminate yourself so eliminate yourself so if you eliminate yourself the low will be pointing to this thereby please go ahead and omit this and write the law

so now I'm left off with just two elements this time I will the midpoint I'm not writing any further medicine which is the element this which is the

left half this which is the right half this because mid is here let's see which is which portion is sorted because I have to check the left portion is sorted because low and mid

are nine and that's true and that's true so the next portion is sorted either left portion thereby what I'll say is

since the left portion is sorted hence I can see one can be compared with Nine and Nine and it is not there so you

eliminate the left half this time eliminate the left half and logos here this time mid goes here and the mid is at one which is which is which is

equivalent to this one hence the element is found hence the element is found and if the element is found you can straight away return the index three and that will be your answer so it's very

important to identify the sorted half then only you can perform a check you cannot just straight away say not lying on the left it'll be on the right or not lying on the right it will be on the left that cannot be said over here got

it okay so time to write down the code so if I have to write down the code can I say I'll always take an array I'll take an n and I will take the element that I have to search so probably I can call it as Target or k whatever you wish

to I've taken it because the first thing that I will do I'll take the low to be zero I'll take the high to be n minus 1.

perfect I've taken the low to be 0 and high to be n minus one what's the next thing I'll be like let's probably do an while of flow less than equal to high

that's all I'll write low less than equal to 1. the next thing will be mid can you figure out your value and maybe we'll say sure why not low plus High by

2 click perfect now the first thing I'll be like okay if I find it there's no need to do any elimination I can straight away stop so if you find it

straight away stop your searching in case you don't find it what's the next thing you have to do identify the sorted half how do you identify the sorted half

either the portion has to be left sorted like either the left half has to be sorted or the right half has to be sorted for the left half to be sorted

can I say the array of flow it has to follow the sorted property which is this if that's the case the left half is sorted or else if that's not the case

the right up will be sorted and is guaranteed either of one-halfs will be sorted you can take up all the arrays because the

the point of pivot like where you rotate it will just be at one section so it is guaranteed so if you look so if you look over here as well the left was not never sorted and the right was always sorted

that is guaranteed either the left or the right will always be sorted so you can take out examples and you can try it out it will always be sure either this or this portion will be sorted so can I

say this that either this or this portion will be sorted so if the left is sorted we will just go ahead and do the elimination similarly so we go and say

okay you are sorted now so tell me if the target is lying within you so this should be the case and and Target should also be lesser than the

mid if that's the case the target lies within you within the left half thereby please go ahead and eliminate the right half or else the target doesn't lies on the

left half thereby eliminate the left half and move right so either I move right or either I move left quite simple same thing you'll do over here on else you'll say okay the right half is sorted

so can I say array of mid has to be less than equal to Target for the Target to lie on the right half and the target has to be less than equal to array of I

for the Target to write lie on the right right half if that's the case then the left portion will be eliminated because the target lies on the right half or else the the right portion will be eliminated

because it doesn't I'm sure it doesn't so I'll go to the left and that's when we end this end is for this particular while loop and this if will contain

these couple of fifths this else will contain this so after this in case you don't find it you say return minus 1 y this minus 1 in case the element is not

there the third space will be exhausted and you'll end up being here and you can straight away return it this is how it will be in case you want to try out the problem you can find the problem Link in the description what I've done is I've

written this exact similar code in C plus plus you can figure out the python Java and JavaScript codes from the link in the description and what will be the time complexity simply performing a binary search

reducing half Alpha logarithmic base to end yes that will be the time complexity and now going back to the sheet done I hope you have understood the entire

problem it's just not about going left or going right like I could have just written the code and said this is the this is the logic go left go right no I explained you how do you basically

approach the problem it's important to understand elimination is the key in most of the problems you have to identify which portion you are sure to eliminate so be

sure if you just identify the portions to be eliminated and then you can write binary search for anything so I hope you have understood the entire problem solving approach just in case you have please please please do consider giving

us that like and if you're new to our Channel what are you waiting for hit that subscribe button right away and yes uh if you haven't followed me on Instagram Twitter and Linkedin all the profile links will be in the description with this I'll be wrapping up this video

let's fill in some other videos and then we're writing don't ever forget your golden I will find it