Search in Rotated Sorted Array ｜ Binary Search ｜ L..
Search in Rotated Sorted Array ｜ Binary Search ｜ L..
Category
📚
LearningTranscript
00:00Hi everyone and welcome to the complete DSA series in which we are going to do an important
00:09question of binary search which is search in a rotated sorted array.
00:12Now if we want to read any other concept in DSA then we will get it in this playlist.
00:19Now let's talk about our question.
00:20This question is called search in a rotated sorted array.
00:23We are given an array which was originally sorted in ascending order.
00:27This array was originally of 0, 1, 2, 3, 4, 5, 6 and 7 numbers which was sorted in ascending
00:34order.
00:35Then this array was rotated from here and the elements were taken to the front.
00:39Because of this, now it has become a rotated sorted array.
00:42And now our array looks like this.
00:44In this array, we have distinct values i.e. all the values are going to be unique.
00:48And in this, we have to search our target.
00:51Now if we want to search the target normally in this array, then its brute force approach
00:55is going to be very easy which will be our linear search approach.
00:57In linear search, what we will do is we will go to each index and find our target.
01:01We will go to the index and find the target and from wherever we get our target, we will
01:05return its index.
01:06In linear search approach, we already know that we need big O of n time complexity.
01:09So this is going to be the time complexity.
01:11But if we want, we can optimize this time complexity more here.
01:15How can we optimize?
01:16There is such information in our question which we have not used yet.
01:20And in programming questions, no information is given extra or like this.
01:24The extra information we have in this question is that our array is a sorted array.
01:28And whenever we want to search a value like target in a sorted array, then we should always
01:33click on binary search once in our mind.
01:36So now we are going to think in the direction of our binary search because binary search
01:42offers us more optimized log n time complexity as compared to linear search.
01:47Now this exact problem is problem number 33 on LeetCode in which we are already given
01:52that we have to write an algorithm with big O of log n run time complexity.
01:55But if we get this question in the interview, then it is not necessary that the interviewer
01:58will tell us to do it in log n.
02:00We have to think by ourselves that the thing like sorted array has been given, it is the
02:04work of searching.
02:05Linear search is fine, it will be easy, but how do I use the sorted thing, we can use
02:10it in the form of binary search.
02:12So in this way, we will start thinking in the direction of binary search.
02:17Now how does normal binary search work?
02:19If our array was completely sorted, then it would be very easy to apply binary search
02:22on it.
02:23In binary search, we take a start, we take an end, every time we calculate our mid,
02:29for our even size array, our mid will be the last element of the first half, so this will
02:34be our mid and we compare our target with mid.
02:36We know that our mid is 3 and our target is 0.
02:38So if the target is smaller than mid, then in that case, I do not need to search in the
02:43right half because there will be even bigger values in the right half.
02:46Similarly, we do not need to search in the left half because our target will exist here
02:50and if it was opposite, that is, if we had 6 instead of 10, then we know that our 6 is
02:54bigger than 3, so we do not need to search in the left half because in the left half,
02:58there will be even smaller values than 3, we will get our answer in the right half because
03:02there will be bigger values there.
03:03So in this way, the logic of our general binary search is applied.
03:07Now when we apply this logic of general binary search on our rotated sorted array, it tends
03:12to fail.
03:13And why does it fail?
03:14For that, let's visualize our array once.
03:19Now we have this array given, if we apply normal binary search on it, then the first
03:24step of normal binary search is to calculate our mid.
03:27To calculate mid, we have a formula start plus end minus start divided by 2.
03:31Now generally, the formula for mid is start plus end divided by 2, but on this, we have
03:35done an optimization.
03:36We discussed this optimization in the last lecture and we said that whenever we have
03:40to find out mid, we will always use this formula.
03:43Once we get mid, for example, for this array, this is going to be the start, this is going
03:47to be the end.
03:48This will be our mid value.
03:49So the first and the simplest step is to compare the target with the mid.
03:54The second step is that if the value of our array of mid is equal to the target, then
03:59what will be our answer in this case?
04:00In this case, our answer will be equal to mid because we got our answer here.
04:04If the target is 6 and here is also 6, then we would have got our answer here, but this
04:08is not equal to the target.
04:09So binary search says that now you have to decide which search space you want to pick.
04:15To pick a search space means that now we have to search in the left half or we have to search
04:20in the right half.
04:21This is the most important decision of binary search because because of this decision, we
04:25get log n time complexity because we decide here and there that I discard my left half
04:31and search in the right or I discard my right half and search in my left part.
04:35So I have to see this decision how it will apply.
04:38Now if we look at normal binary search, then the rules of normal binary search say that
04:42if the value of the target is less than the value of the mid, then discard the right half
04:47completely and search in the left half, but it will fail here because my target 0 exists
04:53in my right half, so it does not make sense to discard the right half.
04:57So here, the rules of normal binary search will not apply, so we will have to find something
05:01else.
05:02We will have to find some other way that how we can pick our search space, which is the
05:06process, which is the most important process, which is the most important logic of binary
05:10search, we can modify that logic a little bit.
05:13So there is an interesting thing for that modification that is always true for a rotated
05:17sorted array.
05:18I am going to talk about that interesting thing.
05:20And the interesting thing is that whenever we see a rotated sorted array, it has a start,
05:25end and mid.
05:26So always if we analyze its left half and right half, then one half of both is always
05:33sorted.
05:34It is already sorted.
05:36I cannot apply binary search on the whole array because I have seen that the whole array
05:40is not sorted.
05:41It has been rotated.
05:42It is not sorted now.
05:43So binary search cannot be applied on the whole array.
05:45But if I find out that one of my left half or my right half is sorted, then I can apply
05:51binary search on whatever will be sorted.
05:53For example, the left half is 345, the right half is 7012.
05:57Can I say that 7012 is not sorted, but this 345 is sorted.
06:01So my binary search can be applied on this left half.
06:05So I can use the conditions of binary search on the left half.
06:09What I am trying to say is that if we are talking about a rotated sorted array, then
06:13in that array, either our left half will be sorted or our right half will always be sorted.
06:20Let's look at its examples.
06:21For example, if we talk about this array, then this is our left half, this is our right
06:25half.
06:26We know that our left half is sorted here.
06:28Similarly, if we take another example of an array, let's suppose we took 60, 70, 10,
06:3320, 30, 40 and 50.
06:36Here, this is our start, this is our end.
06:39If we talk about the mid, then this value is going to be the mid value.
06:43This is the left half of the mid value and this is the right half.
06:46We can see that the left half is not sorted.
06:4860, 70, 10 is not sorted.
06:50But if we look at the right half carefully, then 30, 40, 50 is sorted.
06:53And that is why the right half is the sorted part.
06:56So in any rotated sorted array, either the left half will be sorted or the right half
07:00will be sorted.
07:01When the left half is sorted, then we can apply binary search conditions on the left.
07:06When the right half is sorted, we can apply binary search conditions on the right.
07:11Now, how do we apply binary search conditions on the left?
07:14Let's discuss that.
07:15In this case, we know that our left half is sorted.
07:18So why don't we stand here and check if this target can exist in my left half?
07:24For that, normal binary search conditions can be applied.
07:27Binary search says that if my target lies between start and mid,
07:30because it is sorted,
07:31if the target lies between start and mid,
07:33it means that my target exists in the left half.
07:35And if this does not happen, then my target definitely exists in the right half.
07:40What is the flow?
07:41The flow is basically that if we apply binary search on the left half,
07:44applying binary search on the left half means that we find the target in the left half.
07:48Finding the target in the left half means that
07:50is the value of our target greater than or equal to the array of start
07:53and less than or equal to the array of mid?
07:55Does the target lie between the start and mid of these two?
07:58If it lies between these two,
08:00then we have to go to the left and search to the left.
08:03Otherwise, in the case of else, we have to search to the right.
08:06This is only the case in which we are applying binary search on the left half.
08:10Let me repeat this again because this thought process is very important.
08:14What is the thought process?
08:16For the target, we cannot know whether to go to the left or right by comparing it with mid.
08:21But if I know that the left half is sorted,
08:23then it can tell me whether my target will exist in the left half or not.
08:27If it exists in the left half, then we will go to the left.
08:30And this is the normal condition of binary search to exist in the left half.
08:33And if it does not exist, then it will be the case of else.
08:36In that case, we will go to the right.
08:37Going to the left means that the start will continue next time,
08:40but the end will be mid-1.
08:41Going to the right means that next time our start will be updated to mid-1
08:45and the end will be the end.
08:47So all this work is done when my left half is sorted.
08:51Let's apply this once.
08:52This is my left half.
08:53This is my right half.
08:54We will check if the target lies between 0, 3 and 6.
08:58It cannot lie between 0, 3 and 6.
09:00So where do I have to go?
09:01I have to go to my right half and search.
09:03If we search in the right half,
09:05this will be our search space for the next time.
09:07Now we have to search in this part.
09:09In this part, this will be our start.
09:11Mid will become zero value.
09:13Next time we will do the same again.
09:14We got the start, we got the end.
09:15First, we will take out mid.
09:16We will compare the target with mid.
09:17We got the target here at mid.
09:20We got the answer here.
09:21And we will return mid is equal to 5 index as our answer.
09:25Now let's look at an opposite case of this.
09:27Opposite case means when our right half is sorted.
09:29For that, we can change the values of our array.
09:33Let's suppose this time we have this array given.
09:36In this rotated sorted array,
09:38this will be our start.
09:39This will be our end.
09:41And we will take out the mid value.
09:43This is going to be the mid value.
09:44We will check again.
09:45When we compare this mid with the target,
09:47we will know that mid is not equal to the target.
09:49Now the next step is to identify
09:51whether my left half is sorted or my right half is sorted.
09:54I know that 670 is not sorted in this array.
09:57But 2345 is sorted.
09:59That means my right half is sorted here.
10:01How do we know whether the left half is sorted or the right half is sorted?
10:05In any rotated sorted array,
10:07if our left half is sorted,
10:09can we say that the start value will always be less than the mid value?
10:13If my left half was sorted,
10:15now it is not sorted.
10:16This is 6701.
10:17But here 678 is 9.
10:19Can we say that 6 always comes before 9
10:21and the middle elements follow a single direction?
10:24The condition of left half sorted is
10:26that if the value of the array of start
10:28is less than the value of the array of mid,
10:31or we can write less than equal to,
10:33then this is the condition in which my left half is sorted.
10:36But if this condition is false,
10:38then what will be the other case?
10:41That my right half is sorted.
10:43First, we will check whether the left half is sorted.
10:456 is not less than 1.
10:47That means the left half is not sorted.
10:49That means which will be sorted?
10:51One will always be sorted.
10:53That means my right half is sorted.
10:55Now I have to apply binary search on my right half.
10:57How did I say that one or the other half will always be sorted?
11:01Why?
11:02Because it was already an ascending order sorted array.
11:05If the sorted array is rotated in any ascending order,
11:08then some part of it will always be in increasing order
11:11and the other part will also be in increasing order.
11:13Now we cannot say where this pivot will lie.
11:15But if we take out mid,
11:17then the pivot will always go either to the left of mid or to the right of mid.
11:21If this is mid,
11:23then if our pivot comes to the left of mid,
11:25pivot means from where our array has been rotated,
11:27if the pivot comes to the left,
11:29then it means there is a break in the left.
11:31All the values in the left cannot be sorted.
11:33So the opposite part of the pivot that comes
11:35is always sorted in a rotated sorted array.
11:37Although we will discuss this pivot logic later
11:39when we are talking about quicksort.
11:41For now, we will not discuss the pivot so much
11:43so I do not want to confuse you.
11:45We come back to our normal question.
11:47We know that our right part is sorted.
11:49Now in the case in which our right part is sorted,
11:51we know that I have to apply binary search on the right half.
11:53What does it mean to apply binary search on the right half?
11:55To apply binary search on the right half,
11:57we will search this target between mid and end.
12:00If the target comes between mid and end,
12:02then it means I have to search in the right half.
12:04And if the target does not come between mid and end,
12:06then it means I have to search in the left half.
12:08I have to write the opposite of these conditions.
12:10If we resize them a little,
12:12basically this is the condition
12:14of binary search on the left half.
12:16Now we are going to write the conditions
12:18for how to apply binary search on the right half.
12:20To apply binary search on the right half,
12:22we will check in the right part.
12:24Checking in the right part means
12:26if our target is bigger than the array of mid
12:28and smaller than the array of end,
12:30means if my target comes between mid and end,
12:32then I have to search in the right half.
12:34And if it is not so,
12:36then I have to search in the left half.
12:38So this will be the condition
12:40of binary search on the right half.
12:42Now let's apply this condition practically.
12:44Let's check from the beginning.
12:46Mid is not equal to the target.
12:48Now we will check if the left half is sorted
12:50or the right half is sorted.
12:52I know that my 1 is smaller than my 6.
12:54So this part is not sorted.
12:56This part is sorted in ascending order.
12:58If this part is sorted,
13:00then we will apply binary search on the right half.
13:02Binary search on the right half means
13:04we will check the target
13:07because 0 is smaller than 1.
13:09So I have to search in the left half.
13:11For the next time,
13:13the search space will be this much.
13:15We will search in the left half.
13:17For the next half, the start will be the same.
13:19Mid will be 7 and end will be 0.
13:21We will compare this target with mid again.
13:23Target does not match with mid.
13:25Now I have to check if my left half is sorted
13:27or my right half is sorted.
13:29I saw that my mid is less than or equal to the array of start.
13:31Means it comes before 6 and 7.
13:33So my left half is sorted.
13:35We will check the target.
13:37Does it come between 6 and 7?
13:39No, it does not come between 6 and 7.
13:41Means I don't have to go left, I have to go right.
13:43We used these conditions.
13:45I don't have to go left, I have to go right.
13:47If I have to go right, then mid will be right.
13:49This value is equal to 0.
13:51For the next time, when we go right,
13:53both start and end will point to 0.
13:55This is going to be the start.
13:57This is going to be the end.
13:59Our search space will be different this time.
14:01This 0 will be alone in our search space.
14:03Then we will compare mid with our target.
14:05Both the values will match.
14:07Then we will return our mid.
14:09How does our approach work?
14:11We start with a start and an end.
14:13We take out our mid.
14:15We will compare the target with the mid.
14:17If the target is not compared with the mid,
14:19then we cannot do binary search right now.
14:21But we can find out the sorted part.
14:23First, we will find if left is sorted or right is sorted.
14:25If left is sorted, then we will do binary search on the left.
14:27If right is sorted, then we will do binary search on the right.
14:29So every time,
14:31In our search space,
14:33we will either go left or right.
14:35We are taking that decision like binary search.
14:37But before taking that decision,
14:39we have to find out our sorted part.
14:41Let's write its overall pseudocode.
14:43We are going to start with two values.
14:45One will start equal to 0.
14:47One will end equal to n-1.
14:49We have to run a loop here.
14:51This is our initialization step.
14:53We have to run a loop until the value of start
14:55is less than or equal to end.
14:57We will calculate our mid first.
14:59It will be start plus end minus start divided by 2.
15:01Then we will compare
15:03whether our array of mid
15:05is equal to our target.
15:07If array of mid is equal to target,
15:09then our answer will be mid, which we will return.
15:11Otherwise, we have to check
15:13whether our left half is sorted or right half is sorted.
15:15When will the left half be sorted?
15:17It will be sorted if the value of our array of start
15:19is less than or equal to array of mid.
15:21We don't need to check equal to
15:23because we already have unique elements given.
15:25But for the sake of simplicity,
15:27we have written equal to here.
15:29This is the condition of our left sorted.
15:31If this is not the case,
15:33then the condition of right sorted
15:35will be else.
15:37If left half is sorted,
15:39then we will apply binary search on left.
15:41By applying binary search on left,
15:43we will check whether
15:45our target is greater than or equal to
15:47array of start
15:49and less than or equal to array of mid.
15:51Does target lie between start and mid?
15:53If target lies between start and mid,
15:55then we have to search on left.
15:57Searching on left means
15:59that we will update our end.
16:01The value of end will be mid-1.
16:03This is the condition of normal binary search.
16:05The opposite case is that
16:07we have to search on right.
16:09Searching on right means
16:11that our start will be mid-1.
16:13Similarly, applying binary search on right
16:15means that we are checking
16:17in the second half
16:19that our target does not lie
16:21between mid and end.
16:23If our target is greater than or equal to
16:25array of mid
16:27and less than or equal to
16:29array of end,
16:31then we have to search on right.
16:33Searching on right means
16:35that our start is going to be mid-1.
16:37The opposite case is that
16:39we search on left.
16:41Searching on left means
16:43that our end is going to be mid-1.
16:45Based on these four conditions,
16:47we decide whether to go left
16:49or right.
16:51This is the overall approach.
16:53In this approach also,
16:55we are choosing left or right
16:57in our search space.
16:59As a result,
17:01the time complexity of this approach
17:03will be log-in like binary search.
17:05This is not directly binary search
17:07but it is a modified
17:09form of binary search.
17:11Let's convert this approach
17:13into code.
17:15We already know that
17:17we have this search function.
17:20Initialize with 0.
17:22Initialize with nums.size
17:24minus 1.
17:26We have to run a loop
17:28till the value of start is less than or equal to end.
17:30First of all, calculate mid.
17:32Mid is going to be equal to
17:34start plus
17:36end minus start divided by 2.
17:38First of all,
17:40check if our numsof
17:42is equal to array of mid.
17:44If the value of array of mid
17:46is equal to our target,
17:48let us rename it as target.
17:50In that case, we already know
17:52that we have to return mid.
17:54Otherwise, we have to check
17:56if left half is sorted or right half is sorted.
17:58If left half is sorted,
18:00the value of array of start
18:02will be less than or equal to array of mid.
18:04This is the case of left sorted
18:06and this is the case of right sorted.
18:08In the case of left sorted,
18:10we will apply binary search on left.
18:12In that case,
18:14array of start is less than or equal to target
18:16or target is less than or equal to
18:18array of mid.
18:20In the case of right sorted,
18:22we have to go left.
18:24Left means that end will be updated
18:26to mid minus 1 and
18:28right means that start will be
18:30equal to mid plus 1.
18:32Similarly, if right half is sorted,
18:34we will apply binary search on right half.
18:36Applying binary search on right half
18:38means that array of mid
18:40will be greater than or equal to target
18:42and this target is going to be
18:44If this is the case, we have to go right.
18:46Right means that start is going to be equal to
18:48mid plus 1.
18:50Else, we have to go left.
18:52End is going to be equal to
18:54mid minus 1.
18:56This is the end
18:58of our approach.
19:00If we still don't get the right answer,
19:02we will return minus 1 value.
19:04This is the entire code to apply modified
19:06binary search to search in a rotated sorted array
19:08whose time complexity is equal to login.
19:10Before running this,
19:12we will replace this with a.size
19:14and let's run it
19:16and submit it.
19:18Our solution has been accepted.
19:20If we have completed the lecture successfully,
19:22we can mark our attendance in the comments
19:24and you can also share your progress with me on Twitter
19:26whose link you will get in the description box below.
19:28That's all for today. See you in the next video.
19:30Keep learning and keep exploring.