Search an element in a Sorted & Rotated Array | Binary Search, Part 3 | DSA-One Course #24
Search an element in a Sorted & Rotated Array | Binary Search, Part 3 | DSA-One Course #24
Hey guys, In this video we’re going to solve an important problem on Binary search. It’s called Search an element in a sorted and rotated array. This is a common question in many interviews. We’ll learn how binary search can be modified to solve different kind of real-world problems
🥳 Join our Telegram Community:
Telegram channel: https://telegram.me/realanujbhaiya
Telegram group: https://telegram.me/dsa_one
🚀 Follow me on:
Instagram: https://www.instagram.com/Anuj.Kumar…
Linkedin: https://www.linkedin.com/in/sharma-ku…
Twitter: https://twitter.com/realanujbhaiya
💸 Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!
📚 Complete DSA Playlist: • DSA-One Course - The Complete Data St…
Complete Android Development Playlist: • Android Development Tutorial for Begi…
Hashtags:
#anujbhaiya #dsaone
Ignore these tags:
search an element in a sorted and rotated array
binary search
search an element in sorted and rotated array
binary search in c
search an element in a nearly sorted array
search an element in a almost sorted array
search an element in a sorted and pivoted array
binary search program in c
binary search tree in data structure
search element in a circularly sorted array
search an element in matrix
single element in a sorted array
searching an element in array
Content
0 -> hey what's up guys! Anuj here and welcome to the DSA one course.
1.929 -> And in today's video we're going to talk about a very important question based on Binary search.
5.457 -> This question has been asked a lot of times in the interviews.
7.671 -> So, we're going to understand it very clearly.
9.268 -> Question is to find an element in a sorted and Rotated array.
12.702 -> An array is given to you, which is sorted as well as rotated. I've given some examples here.
17.5 -> Here, if this array was sorted--- 40, 50, 90, 100,110 and then I have written 120, 130 later on.
26.073 -> So, we've rotated this sorted array twice.
30.026 -> So, it might be rotated twice in the question, 4 times rotated
33.814 -> 0 times rotated, which means the entire array is sorted.
36.449 -> We'll take all the cases in account.
38.771 -> Similarly, if you see this array, would be sorted as well
41.212 -> here it has been rotated 4 times. So it was rotated at this position--20, 30, 40
46.371 -> then 50, 60 90, 100
48.614 -> Similarly, in this 3rd array, which was also sorted but it has been rotated at this position.
53.605 -> So, this array has been rotated 5 times. So, let's think how we're going to do it.
57.187 -> First of all, we're going to apply brute-force in it.
59.843 -> Brute- force means, traverse all the elements once and as soon as you get your element, you'll return its position
65.729 -> For example, we've to find 100 here. So, we got 100 at this position therefore we returned this position.
70.043 -> This was the brute-force. Its time complexity would be O(n).
74.036 -> We can do it even lower than this, because your array was sorted, right!!
78.686 -> So, we can benefit from that.
80.243 -> We know binary search is applied when array is sorted and you know the left and right Index between that sorted array.
86.386 -> Here, you don't know, if the array is entirely sorted. This is your left position and right position but your array isn't sorted between them.
94.911 -> So, here a modified version of Binary search will be applied. That is why it is a favorite question
99.957 -> of interviewers. Because modified binary search is applied here.
103.065 -> And people often stumble upon modified binary search, that is why it is asked many times.
107.744 -> So, we're going to understand it very clearly.
109.014 -> Think how can we do it and then I'll tell you.
110.943 -> The basic of binary search that will be applied here, is that, you've to come to the middle element
116.957 -> And then we've to check if the left part from the middle element is sorted or not
121.029 -> How? If the firstmost element on the left is smaller than the mid value
127.266 -> then left part is sorted otherwise its not. Right!!
130.871 -> Here, you can see that our left part is sorted from the middle element
134.682 -> and since this element is smaller than this element, that is why we know that left part is sorted
140.5 -> Right!! And here as well, left part is sorted as the first element is smaller than the mid value.
147.198 -> So, we know that we can check through middle element if the left part is sorted or not.
151.329 -> If the left part isn't sorted, then you can guarantee that right part is sorted.
158.029 -> So, as you can see this part---90 to 110, this part is sorted as left part isn't sorted.
163.477 -> As this is the rotated array, if left part isn't sorted, guaranteed right part is sorted.
169.741 -> Just think, as I am saying.
171.445 -> You'll understand.
172.64 -> We know now that Binary search can be applied on it, because one of the left or right part is sorted.
178.814 -> If we know that our left part is sorted and our element can be in the left part, then we'll discard the right part and move to the left part
187.244 -> I'm saying that, suppose this is your array and we know that left part is sorted, 50 100
192.286 -> and the element that we've to find, suppose the key is 60
196.518 -> Now, we've to check, if the 60 is present in this left part or not. To check we'll
201.914 -> We'll check from 50-90, if our element lies in this range, then you'll see
207.443 -> Yes, 60 is greater than 50 and smaller than 90
210.158 -> which means will eb in the left part instead of the right.
213.554 -> Are you understanding this point?
214.445 -> Similarly, let's see for this example as well. Suppose here, our key is 5
221.4 -> then, first of all we'll check through this middle element if left part is sorted
226.199 -> So, we'll know that left part is sorted.
228.369 -> Because 20< 50, which means left part is sorted.
231.574 -> Now, we'll check if our key lies in our left part or not.
236.314 -> For that, we'll check if the key element is greater than 20 and smaller than 40, no its not
241.986 -> which means our element is not present in the left part,
244.672 -> therefore we'll discard the entire left side and we'll call the same recursive function again.
249.626 -> Here, the logic of binary search is applied. Similarly, for this example
253.481 -> We know that, left part isn't sorted, right part is sorted and the element that we've to find is 100.
258.557 -> So, we came to the left side which isn't sorted. We know that right part is sorted, so we'll check the key that we've to find
266.986 -> exists in the right part or not
268.914 -> means is our key greater than 90 and smaller than 110? Yes, it is.
272.582 -> If yes then, call for this part and discard the left part entirely.
277.755 -> Every time, we're discarding either the left or the right part entirely. So I'm going to code it.
283.443 -> You all think as well how is it going to be coded.
285.114 -> and it'll be clear to you all with the code. Then we'll dry run.
288.968 -> So, I've coded it entirely here. I've done it in iterative way, if you want you can try to do it in recursive way yourself.
295.071 -> You've got an array and a key. You've to find the index of that key and return the integer value.
301.251 -> low =0 and high =a.length-1
304.329 -> so, it'll be from 0 to (n-1). After that---while( low < = high )--- till then we've to run it
310.171 -> So, we'll run this example. We're going to apply all the steps that I told you earlier.
315.142 -> First of all, we'll check--here normal binary search is running. this much part is normal Binary search, right!!
319.814 -> We must remember it, this much part is our normal binary search. First we find the mid element which is --> (low + high / 2)
326.371 -> then if middle element is equal to key, then we return the mid position
330.786 -> now, it'll be a little modified down here. How is it being done?
333.986 -> First we'll check, if the left part is sorted. If this condition is true then, we can say that left part is sorted
338.714 -> if this condition is not true, which means it is --else-- then we can say that right part is sorted
342.6 -> I've already explained it to you
344.043 -> if (a [ low ] < a [ mid ]---so, first let's find the mid
348.729 -> 0,1, 2, 3, 4, 5, 6
353.726 -> So, our mid element will be
355.595 -> mid = 0+ 6/2 =3; So mid element is 3, we came here
362.629 -> then we'll check--if a[ low ]< a [ mid]---then yes, 20< 50, which means we can say that left part is sorted and we can see that as well
370.6 -> Now we'll check, if our key is present in the left part. For that, we'll do
374.801 -> if (key > = a [ low], right!!!
377.4 -> if key is greater than 20 and also if the key is smaller than mid. So, here key is not even greater than 20
383.231 -> we'll come out of this loop and go into else. We'll say-- low= mid +1
387.957 -> So, we can say that if key is not present in this range then we can discard this entire range entirely.
394.569 -> and for the next binary search, our low will be mid +1. Now, binary search will from 60 - 10
400.014 -> we discarded the left part entirely.
402.298 -> I did the same here, low = mid +1. So earlier, low was 0
408.187 -> and high was 6, from where the mid was 3, now our low will be +1 to 4.
415.543 -> Now we'll try to find between 4 -6. So we'll go into the loop again--while ( low < = high)-- yes 4 < 6
421.717 -> so we'll find the mid which is 6+ 4 /2 = 5
426.386 -> So, we got our mid. now we'll check if the middle element is equal to 5, yes it is. We'll return from here.
433.543 -> Suppose, you had to find 10 instead of 5. Let's take it a little further
438.971 -> Suppose you had to find 10, then we didn't get the middle element. Its 5 but key is 10
444.835 -> then we'll check if ( a [low] < a [ mid ])
448.205 -> low is 4 and mid is 5, right!!! then a[ low] is not less than a[mid], which means left part isn't sorted
454.067 -> So, left part isn't sorted which means right part will be sorted, which is actually sorted--5, 10
460.243 -> the we'll come into this one and we'll check---if ( key > a[mid] && key < a[ high])
465.615 -> means if the element that we had to find---10--lies in this range? Yes it is
472.186 -> key > a[ mid] && key < =a[ high]
477.729 -> because it can be equal to high, otherwise this case would have been missed here. It will be equals at both the places
483.257 -> but I've written here less than and greater than because we're already checking it with the middle element
487.244 -> So, we'll come to this range because this condition will be true, then it'll be low = mid +1
491.343 -> so, low will be mid +1. Mid is 5.
493.957 -> mid +1 will be 6.
495.986 -> again, we'll come here--while ( low< = high). Then yes it is < = high.
500.009 -> since it is 6 at both the places, mid will be 6+6 /2 =6
504.571 -> and then we'll compare it with the mid element
506.366 -> so--if a[mid] == key---so both are 10. We've got it and we'll return this position
514.029 -> So, in this way dry run is being done. Let's do some more examples because we've to learn to maintain edge cases properly.
519.511 -> So ,let's maintain the edge case. Let's take more examples
523.175 -> let's assume we've to find the 20 as the key
527.571 -> so, we'll try to find 20. How can we find it?
530.322 -> again, low = 0 and high = 6
536.292 -> So, mid will be 3
540.143 -> Mid is 3 and we'll check if the left part is sorted, yes it is. And we'll check if this element is present in this range between 20 -40
547.869 -> So, yes this element is present between 20 -40. We'll discard the right part entirely and high = mid -1
557.386 -> It'll be updated from 6 to 2. So, earlier it was 6 and now it is 2. So our range is from 0 - 2
562.436 -> now, we'll find the mid which is 0+2/2= 1
565.514 -> middle element is this one.
567.571 -> and we'll check if it is mid element. No, its not. We'll check if the left part is sorted, yes it is.
573.486 -> along with that if the mid element lies in the left range, then, yes it does lie in the range.
578.414 -> If it is like that then, again our high will be (mid-1)
582.631 -> high will be 1-1= 0
584.594 -> High =0 and low =0, now we'll check and mid will also be 0
588.638 -> and we'll get the mid element
591.157 -> So, it is working in this way. Suppose we are trying to find such an element which is not even present in this array, which is (-5)
597.957 -> we know that -5 is not present in this entire array. So it should return -1, as this element is not present in the array
604 -> so, again low = 0 and high = 6
607.529 -> mid =3
609.129 -> mid = 3 then we'll check, if the left part is sorted, then yes it is. Does -5 lie in this range? No it doesn't.
616.429 -> which means it won't be there in the left part.
619.404 -> Then we'll go to the right part, our low = mid +1
623.107 -> low = 3+1 = 4
625.603 -> now we'll try to find between 4 -6, so mid = 4+6 /2 = 5
632.114 -> now, we'll check if it is equal to the id element. No, it is not
637.014 -> We'll check, if the left part is sorted, no its not, instead right part is sorted.
642.569 -> then we'll check if the key lies in this range, no it doesn't.
647.592 -> which means high = mid -1
650.114 -> so, high = mid -1. Mid was 5, so mid -1 = 4
654.386 -> so low and high both are 4. Now if we'll find its mid then it'll also be 4
658.386 -> and we'll check if it is equal to the mid element. Since one is 60 and key is -5, so its not equal.
664.792 -> So, no we'll come here--if a[low]< a [mid}]. Everything, low , high and mid are same
672.2 -> then here the corner case is also there. So, then corner case should work properly. We'll check
677.171 -> if a[low ] < a[ mid]--then a[low] is 60 and a[ mid ] is also 60
682.171 -> then a[low] is not less than a[ mid], right!!!
684.946 -> because 60 is not less than 60
686.817 -> So, we'll come to the else condition. Here, you'll check--if (key> a[mid]----
691.588 -> so, is -5 > 60 and -5< = 60?
696.727 -> we can see that one condition is failing here, right!!! this condition, since -5 is not greater than 60
701.883 -> then , you'll come into else, then high = mid -1
705.332 -> then, high will be mid -1. Mid was 4 and it'll be updated from 4 to 3
710.171 -> Now you'll come into this while loop and check ---low
716.838 -> as soon as you'll come out of the loop, you might not be able to see there, so I'll write it here
721.595 -> as soon as you'll come out of this loop, you'll write return -1
725.643 -> and here your function will end. Its ending from there till here.
728.948 -> I've written this (return-1) after this while loop ends
732.186 -> which means if it couldn't return from here, then you cannot return from the entire iteration
737.604 -> which means element is not present anywhere
738.913 -> so, finally you'll come out of this value, return -1 and say that this element is not present
743.114 -> So, this was the question. It is an important question, you might have seen as well. Understand it very clearly.
748.108 -> Be thorough with it. It might be asked from you many times in the interviews.
752.919 -> With that, let's end this video here, if you liked this video then do like it.
756.528 -> Do subscribe to the channel. I'll meet you all in the next video.
759.262 -> Bye! Bye!
Source: https://www.youtube.com/watch?v=Le8bc8aHgBA