- 8 minutes ago
Transcript
00:00The next question we will talk about is search in a rotated and sorted array
00:04It is a question of medium-level
00:05It is very important in interviews and it is very important to understand it
00:11And this question is not difficult
00:12In fact, it is easy to find binary search
00:17But we have to handle all the cases
00:21So we have to handle many cases
00:23So handling them is the important part
00:26It is not difficult, it is easy to think about binary search
00:30We will use the concept here
00:32And just focus on the cases
00:33We will handle all the cases
00:35The question is that we will give a sorted and rotated array
00:40In which there will be distinct elements
00:42It is different
00:44It is not that if there are 1, then there will be 1
00:47There will be duplicate elements
00:49If there will be 1, then there will be 1
00:50If there will be 2, then there will be 1
00:56This array is the ascending order
00:58For example
00:59I have also given this array
01:00This array was originally sorted in ascending order
01:04Then what did it do?
01:05I rotate it in a pivot point around
01:07Like I rotate my pencil
01:08I rotate it in a pivot point around
01:09I rotate it in a pivot point around
01:13What does it mean?
01:16For example, I have an array
01:171, 2, 3, 4, 5
01:20This is a sorted array
01:21This is an ascending order
01:22There is a sorted array
01:23There are distinct elements in it
01:25They are matching all the properties
01:27Now what did it do?
01:28I have taken this 3 as a pivot
01:30And I rotate it around
01:33What will it be?
01:34This is 4 and 5
01:35This portion will come up
01:38From rotation
01:39This portion will come up
01:41This array will convert to 4, 5
01:44Then we will come up
01:45So this portion will come up
01:48And this portion will come up
01:51This portion will come up
01:52So this is the pivot
01:53Round rotation
01:543 is coming up
01:55Last
01:56My pivot is remaining in last
01:57And I rotate it in the array
02:00I rotate it in the array
02:01The same thing is in my question
02:03In my question
02:05There is a sorted and rotated array
02:07Now what do I do?
02:09I want to find an array
02:10I want to find an element
02:11I call it my target element
02:13I want to find out
02:14I want to find out
02:14I want to find out
02:15I put 0 here
02:16So in my array
02:17Where is my 0
02:19Where is my index?
02:20I want to return its index
02:23This index
02:24This is 0
02:24This is 1
02:24This is 2
02:25This is 3
02:25This is 4
02:26This is 5
02:26This is 6
02:37It looked like
02:38The 0
02:391
02:402
02:41Then
02:41Four
02:43Five
02:44And
02:44Seven
02:45This is 5
02:45What has made it?
02:47It puts 2 as a pivot
02:49And placed this 4 elements
02:51It is rotated
02:53Now
02:53For solving the question
02:55For linear search
02:56What does linear search mean?
02:59The meaning of linear search
03:00Is there a target here?
03:02I go and find the target here
03:03I go and find the target here
03:03I go and find the target
03:04I go and find the target
03:07if my target exists there, it can be solved in that way.
03:12I know that my target exists in index 4, so I will return 4.
03:16But why don't we solve it with linear search?
03:18Because linear search is big of n.
03:21We have to solve it in n log n.
03:24And how do we solve it?
03:25Using divide and conquer.
03:29So we have to solve it in less time.
03:32We have to solve it in an optimized way.
03:34So we will use a different approach.
03:39Which will be a modified binary search.
03:43Modified binary search means that binary search will be different.
03:49First of all, let's understand some things.
03:51My array, can I represent this array in a diagram?
03:56I mean, can I place my elements here in a diagram?
03:58I will place my 4 here, my 5 here, my 6 here and my 7 here.
04:07So what will happen?
04:08It can be a straight line.
04:09Where to where?
04:10Where to where?
04:10Here to here.
04:11I can say my line 1.
04:14After that, I will plot it from 0.
04:17Here I will plot it from 0.
04:19Here I will get my 1.
04:20Here I will get my 2.
04:21What can I say?
04:22This is my line 2.
04:25Here I have an element here, here and here.
04:28And I have 4 elements here.
04:30So when I have a sorted and rotated array,
04:33I always have 2 lines.
04:35This line is always increasing.
04:37And this line is always increasing.
04:39Now these two lines are possible.
04:41And this line is always increasing.
04:42In this case, it's not maintaining.
04:43So this line is just in this way.
04:47So this line stays in this way.
04:47Where this line goes down from here and here.
04:51And this line goes down from here.
04:52And it can be possible that these points are always up to this point.
04:56Or equal to it.
04:58So here also, there will be a slope that is made down.
05:01So diagrammatically, I can visualize this problem or this array in this form.
05:06I can visualize it.
05:07And this visualization is very important.
05:09When I have visualized it in the form of diagrammatically,
05:11there will be all my cases that I have to handle.
05:15Now if I have any target given me,
05:18then I can say that my array will be a starting index.
05:23It will be a ending index.
05:25Now I have to follow a binary search approach in this question.
05:28So I can say that I will remove mid.
05:31Mid is starting index plus ending index by 2.
05:34Or starting plus ending minus.
05:36The other formula is also available to remove mid.
05:38We can also use this.
05:39I always have an array of mid.
05:43This array of mid.
05:45I will have two cases for mid.
05:47Either my mid is line 1,
05:49or mid is line 2.
05:50What can I say?
05:52Either my mid can come here.
05:54Or it can come here.
05:56Either it can come here.
05:57Either it can come to line 1 or line 2.
05:59What will my mid value come to this case?
06:02If I have a mid value come to this case,
06:02my mid value will be 7.
06:04Where will my mid lie?
06:06My mid will lie on line 1.
06:08If I have an array of 2.2, 2.5, 2.8, 3.4 elements come to this way.
06:16Then my mid comes to 2 or 1.
06:19I will lie on this line.
06:21So there are two cases.
06:22Mid value will lie on line 1 or line 2.
06:25I will lie on the mid value.
06:26First, let's talk about case 1.
06:28Case 1 is the case 1.
06:29It is the case 1.
06:31It is the case 1.
06:32It is the mid value.
06:33I will lie on line 1.
06:34Then I will compare my mid target to mid.
06:38If my target is greater than starting index.
06:42Or equal.
06:43And my mid is small.
06:45Where will I lie on the mid?
06:47I will lie on the left mid.
06:50If the mid is here.
06:51And target size.
06:53Th� is the mid.
06:54If the mid is small.
06:54It be薄 b Metroid.
06:55If the mid is smaller and higher from starting index.
06:56So he will lie on line 1.
07:00If the 11th case 1 has too.
07:02Then it will lie on line 1.
07:02This case 1 has too.
07:03So then my target will lie on line 1.
07:05What is the next case.
07:08Its value, the other condition not true.
07:10Where will this value lie will lie on that point?
07:12This case.
07:13It will lie inside right.
07:15Where the condition falls.
07:17Which is the main point just made it.
07:20Now let's talk about line 2. If I put my mid line 2 somewhere, what can I say in it?
07:27That my target is greater than mid and equal to ending index.
07:33That means it will be greater than mid and less than ending.
07:37Where will I put it?
07:39It will lie in my line 2.
07:43No, it will lie in my left if this condition falls.
07:47I will visualize it in a little better way.
07:51Every time I have starting index and ending index, I will remove mid.
07:57In this area, I will put my line 1 in mid.
08:00In other areas, I can plot my elements in this way.
08:07I will put it on line 1.
08:11This is my line 1.
08:12In other areas, I will put it on line 2.
08:16This is my line.
08:17If I increase it, I can go to line 2.
08:24Now I have taken the first case, which I put the mid here.
08:28I will put it on line 1.
08:35In this case, I will have a case A and a case B.
08:40What is the case A?
08:42In case A, when I have my elements here, I have to search my target here.
08:49When I will search my target here?
08:51When I will search my target here?
09:03The case A will come from line 1.
09:06As I have identified mid, I will put it on line 1.
09:10One will be left and one will be right.
09:12When I will search my target in left part?
09:14When I will search my target value, which I will search,
09:17I will put it on starting index and under mid.
09:21When I will put it on line 1, what will happen?
09:26So what will my case A come from here?
09:28The case A will come from line 1.
09:32What is the condition?
09:34The condition is that the target value is greater than or equal to starting index,
09:38but less than or equal to mid.
09:40And above all the other cases, my case B will come from line 1.
09:44The case B will say that we have to search the right part of line 1.
09:49If this condition is not true, if this condition is false,
09:52then where do I search?
09:54I will search in this small part.
09:56Then what will I do?
09:57I will search in mid and right.
09:59In the mid part, this part also comes in this part.
10:03So this part will be true, small part.
10:05No, what will happen?
10:06I will search in large part.
10:08So this is not just line 1.
10:10It will become mid and right.
10:13This will become mid and right.
10:15Besides, I have case 2.
10:18Case 2 says that my mid is on line 2.
10:22I will put it on line 2.
10:24What does it mean?
10:25I will put it on line 2.
10:27I will put it on line 2.
10:28This is my mid value.
10:30What can I do?
10:32I can check for mid.
10:33I need to search here.
10:36I will search here.
10:37This is the right part of line 2.
10:39Line 2.
10:40The right part is that if my target value is greater than mid,
10:43it is greater than mid,
10:43but it is greater than the ending index.
10:46It will be lower than the end index.
10:47So I will put it on line 2.
10:51So I will put it on line 2.
10:52Case C says that we are going to line 1.
10:54We will go to line 1.
10:55In that case, my target value will be greater than mid.
11:00And my ending index will be greater than the end index.
11:03And what will be case D?
11:04Case D will be the left case.
11:07Where we are going to else.
11:11Now the left is the mid.
11:12We are going to search in this whole portion.
11:15If it comes to right,
11:16it will get in this whole portion.
11:17If it comes to else,
11:18then I will search in this whole portion.
11:20So I have 4 cases.
11:22What is the case?
11:23Case 1 is the mid value is on the left one.
11:26But within that,
11:28my target is the starting index.
11:31So I have to search in line 1.
11:33If not, I have to do mid and right.
11:35Case 2 is the mid.
11:37I will search in line 2.
11:38I have to search in this case.
11:39I have to search in line 1.
11:40I have to search in line 1.
11:42That will search in condition.
11:44If not,
11:45then I will search in mid.
11:49I will search in line 1.
11:50Now I will know how to do mid line 1.
11:53I will put in line 1.
11:54Then I will put in line 1.
11:55When my array of starting index
11:58will be less than equal to mid.
12:00What does it mean?
12:02Let me put in line 1.
12:04Now I can say that my starting index is always lower than mid because the slope of the first line
12:12is like this.
12:14So the slope is like this means that this line is always going to the top because the elements are
12:18in ascending order.
12:19So the value of starting index and mid will always be small.
12:27So if this condition is true then my mid is on line 1.
12:31What does it mean to line 2?
12:34It means that if my mid is here then I can say that it will always decrease the value of
12:39the ending index.
12:41Or it will be equal.
12:43Or the mid will come here.
12:45Or it will decrease the value of it.
12:46Because the second line will always be slow.
12:49So the value of mid is less than equal to my ending index.
12:52So the condition here is that my array of mid.
12:56I mean that the element lies on mid.
13:02The value of mid is always less than the array of ending index.
13:06So I have 4 cases.
13:08The first case comes when I have line 1.
13:10If I can put a middle of the date.
13:11I mean that my mid will have something here.
13:13The starting index value will be less than the mid or equal.
13:16Then I will identify the case 1.
13:18I will search the middle of the date on the left.
13:20It means that there is the mid here.
13:21So I can search the middle of the date on the date.
13:24So I will search the middle of the date on the left.
13:34When the condition is true.
13:35No, then I have to search on the left.
13:38For this, we write code.
13:40And if we write code, we will see it again and again,
13:43then it will be easier to understand.
13:45And it's like code is binary search.