1 00:00:01,750 --> 00:00:02,469 Hi, everyone. 2 00:00:02,500 --> 00:00:10,360 So today we are going to solve this question so much in our SO today, OK, so let us consider an example. 3 00:00:10,370 --> 00:00:12,250 So this is basically a sword, Tonetti. 4 00:00:13,160 --> 00:00:19,190 OK, so this is basically a of one, two, three, four, five, OK, and what is the meaning of rotation? 5 00:00:19,440 --> 00:00:23,060 So let's say this area is rotated around with three. 6 00:00:23,100 --> 00:00:27,760 OK, so these are two parts of the area. 7 00:00:27,770 --> 00:00:32,530 And I don't suppose this area is rotated around the pivot tree. 8 00:00:32,870 --> 00:00:38,420 Now, after the rotation, this will be my new area, three, four, five, and then one, two. 9 00:00:38,840 --> 00:00:40,600 OK, so this is the example. 10 00:00:40,610 --> 00:00:43,670 Basically, this is the example of a rotated artillery. 11 00:00:44,830 --> 00:00:50,560 OK, so this is an example of what he did today and now what we have to do, so basically we have to 12 00:00:50,560 --> 00:00:52,870 search inside our attitude for today. 13 00:00:53,050 --> 00:00:54,440 Let us consider an example. 14 00:00:54,790 --> 00:00:56,950 So these are three rotated. 15 00:00:56,950 --> 00:00:59,680 So that is and these are the target values. 16 00:00:59,680 --> 00:01:03,780 And we have to find out what index these target values are positioned. 17 00:01:04,610 --> 00:01:08,530 OK, so three so three is present at this index. 18 00:01:08,540 --> 00:01:12,850 So this is basically zero one, two, three, four, five, six and seven. 19 00:01:13,120 --> 00:01:14,590 So this is index seven. 20 00:01:15,010 --> 00:01:17,620 So today is not present inside this area. 21 00:01:17,620 --> 00:01:21,880 So index will be minus one, I answer will be minus one and four zero. 22 00:01:21,910 --> 00:01:24,610 So this is zero one, two, three and four. 23 00:01:24,940 --> 00:01:27,330 So this is present to the respondent at index four. 24 00:01:27,550 --> 00:01:31,060 OK, so the input will basically be adulterants auditory. 25 00:01:31,510 --> 00:01:37,300 So input will basically be out of disordered area and our target value and we have to find the index 26 00:01:37,300 --> 00:01:39,130 at which the target value is present. 27 00:01:39,210 --> 00:01:45,730 OK, and the assumption is basically there are no duplicates, OK, so there are no duplicates inside 28 00:01:45,730 --> 00:01:46,510 the array. 29 00:01:46,510 --> 00:01:48,640 All elements are basically unique elements. 30 00:01:48,670 --> 00:01:50,560 OK, so all the elements are unique. 31 00:01:50,800 --> 00:01:55,300 Now, before starting solving this question, I want to discuss this question one more time. 32 00:01:55,750 --> 00:01:59,260 So in this question, let's see if this question has been modified. 33 00:01:59,590 --> 00:02:04,590 So instead of finding the first and the last occurrence, let's say, I want to find how many times 34 00:02:04,600 --> 00:02:05,620 a human element appeared. 35 00:02:05,680 --> 00:02:12,540 OK, so I have to count the occurrences of an element count occurences of an element. 36 00:02:13,060 --> 00:02:14,590 So here it. 37 00:02:14,680 --> 00:02:17,380 So how many times it is appearing in this area. 38 00:02:17,410 --> 00:02:19,140 So it is appearing two times. 39 00:02:19,390 --> 00:02:21,000 So how many times six is appearing. 40 00:02:21,010 --> 00:02:22,160 So it is not pleasant. 41 00:02:22,180 --> 00:02:23,690 So it is appearing zero times. 42 00:02:23,750 --> 00:02:27,900 OK, so what is the function so that the function will be integer. 43 00:02:28,660 --> 00:02:31,630 Because I have to return the count of occurences. 44 00:02:31,660 --> 00:02:37,090 OK, function will be integer, the input will be a vector in the target value. 45 00:02:37,390 --> 00:02:42,660 Now instead of returning instead of creating understanding of actor since I have to return count. 46 00:02:42,670 --> 00:02:43,870 So what will be our answer. 47 00:02:43,900 --> 00:02:44,830 So I will return. 48 00:02:47,160 --> 00:02:52,570 Last I know the last position, last minus, first plus one. 49 00:02:52,990 --> 00:02:56,430 OK, so the question is count the quantity of an element. 50 00:02:56,430 --> 00:02:57,570 This will be my answer. 51 00:02:57,780 --> 00:03:00,180 Last minus first plus one you can see here. 52 00:03:00,570 --> 00:03:04,950 So the last position is basically for the first portion is basically three. 53 00:03:05,280 --> 00:03:08,100 So four minus three plus one. 54 00:03:08,460 --> 00:03:11,340 So this is basically two and two is our answer. 55 00:03:12,030 --> 00:03:18,450 OK, so I will return last minus first plus one and how to find lost and how to find first that we already 56 00:03:18,450 --> 00:03:20,360 know because we have solved this question. 57 00:03:20,660 --> 00:03:25,130 OK, so I will be able to solve this question and log in time. 58 00:03:25,190 --> 00:03:29,180 OK, so for counting the occurrence of an element inside today. 59 00:03:30,390 --> 00:03:31,530 And so did ready. 60 00:03:32,040 --> 00:03:33,450 So this is the approach. 61 00:03:33,670 --> 00:03:34,890 Find the last element. 62 00:03:34,920 --> 00:03:39,990 Find the first element returned last night as first blessin time complexity will be Logan and the space 63 00:03:39,990 --> 00:03:41,260 complexity will be open. 64 00:03:41,700 --> 00:03:44,880 OK, now, at this point, so first is minus one. 65 00:03:44,910 --> 00:03:45,420 So what? 66 00:03:45,420 --> 00:03:46,250 I will return here. 67 00:03:46,380 --> 00:03:48,720 So basically I will return here. 68 00:03:49,100 --> 00:03:49,650 Zero. 69 00:03:49,680 --> 00:03:54,850 OK, so you can see for six the first and the last boat will be minus one. 70 00:03:55,170 --> 00:03:56,950 So six is not abating. 71 00:03:56,970 --> 00:04:00,120 So at this point I will return zero and add this line. 72 00:04:00,120 --> 00:04:02,190 I will return last minus first plus one. 73 00:04:02,370 --> 00:04:05,250 OK, now let's come back to our current question. 74 00:04:06,440 --> 00:04:11,730 OK, so our current question is basically we have to solve China rotated certain Eddie. 75 00:04:12,340 --> 00:04:15,470 OK, let's see how we can solve this question. 76 00:04:16,860 --> 00:04:19,320 So let us let us draw some diagram. 77 00:04:19,980 --> 00:04:21,899 OK, so we have assorted Eddie. 78 00:04:21,930 --> 00:04:24,240 OK, so foresighted, Eddie. 79 00:04:28,530 --> 00:04:29,910 So this is I saw today. 80 00:04:30,170 --> 00:04:32,050 OK, so this is I saw today. 81 00:04:33,510 --> 00:04:37,380 These are elements that say this is one, this is two and so on. 82 00:04:37,480 --> 00:04:39,120 Let's say this is basically 250. 83 00:04:39,570 --> 00:04:41,640 OK, so this will be the diagram for us. 84 00:04:41,650 --> 00:04:42,180 Ordinary. 85 00:04:43,770 --> 00:04:45,400 OK, now what is the question? 86 00:04:45,420 --> 00:04:48,990 So question is basically this area has been rotated. 87 00:04:49,030 --> 00:04:51,480 OK, let's say this area has been rotated. 88 00:04:51,810 --> 00:04:57,480 So this part will come here and this part will go there. 89 00:04:57,870 --> 00:04:59,340 OK, so what the diagram. 90 00:05:00,700 --> 00:05:02,170 Sodergren will be very simple. 91 00:05:05,010 --> 00:05:12,600 First, this part, so this is this part and then this part. 92 00:05:13,860 --> 00:05:15,420 OK, so basically. 93 00:05:18,180 --> 00:05:23,790 This part, OK, so let's take this elementary, let's say 50. 94 00:05:24,870 --> 00:05:26,520 And this element is led to. 95 00:05:27,240 --> 00:05:33,060 So I have 60 here again, I have 250 here, then the settlement 50. 96 00:05:33,060 --> 00:05:36,630 So I have 50 here and then I have one here. 97 00:05:37,110 --> 00:05:40,230 OK, so this is basically a sorted at. 98 00:05:41,630 --> 00:05:44,120 So this is rotated, so did Eddie. 99 00:05:46,690 --> 00:05:54,560 OK, so in certain areas, so this is my new start point and this is my new end point in this case. 100 00:05:54,580 --> 00:05:58,700 So this is my start point and this is my end point. 101 00:05:59,110 --> 00:06:04,590 OK, so now in this case, this is start and this is and and you can notice here. 102 00:06:04,900 --> 00:06:07,870 So basically start will always be good then end. 103 00:06:08,410 --> 00:06:10,330 OK, so start with bigger than end. 104 00:06:10,330 --> 00:06:10,610 OK. 105 00:06:10,630 --> 00:06:13,240 So basically this will be the situation. 106 00:06:14,640 --> 00:06:17,320 The end point will always be lost in this start point. 107 00:06:17,750 --> 00:06:19,950 OK, if you want, you can draw one diagram. 108 00:06:20,440 --> 00:06:21,810 OK, let us take an example. 109 00:06:22,270 --> 00:06:24,080 Let's take three, four, five, one, two. 110 00:06:24,210 --> 00:06:24,960 OK, so. 111 00:06:26,610 --> 00:06:32,880 Let us draw one more time so that you can understand what will be our diagram look like, and our ETA 112 00:06:32,880 --> 00:06:36,750 is basically our is initially basically one, two, three, four, five. 113 00:06:38,990 --> 00:06:45,620 OK, so for one, two, three, four, five, let's say this is my element, so this is basically one. 114 00:06:45,620 --> 00:06:50,240 This is two, this is three, this is four and this is basically five. 115 00:06:50,270 --> 00:06:53,330 OK, and now this area has been rotated. 116 00:06:53,330 --> 00:06:57,510 So what it will become so it will become three, four, five, one and two. 117 00:06:57,990 --> 00:07:01,640 OK, so this will be deconditioned. 118 00:07:05,900 --> 00:07:10,940 So this is basically three, this is basically four, this is basically five. 119 00:07:12,080 --> 00:07:15,350 This is basically one, and this is basically two. 120 00:07:16,910 --> 00:07:23,630 OK, so in the above example, I did a mistake, so this will be basically one and this will be basically 121 00:07:23,630 --> 00:07:24,080 50. 122 00:07:24,240 --> 00:07:26,390 OK, so I'm sorry. 123 00:07:26,690 --> 00:07:29,350 So this will be one and this is basically increasing. 124 00:07:29,360 --> 00:07:31,210 OK, so this is one side increasing. 125 00:07:31,220 --> 00:07:33,320 And here also the elements are increasing. 126 00:07:33,470 --> 00:07:33,830 OK. 127 00:07:36,430 --> 00:07:37,960 Now, how against all this caution? 128 00:07:39,350 --> 00:07:44,300 So I hope you understood what we'll be able to discuss today so that it is hard that it will look like 129 00:07:44,300 --> 00:07:44,630 this. 130 00:07:47,590 --> 00:07:50,120 So this will be a general diagram for outrated sorted. 131 00:07:51,160 --> 00:07:51,940 So let's say. 132 00:07:53,400 --> 00:07:56,640 This ad is basically increasing order and then. 133 00:08:00,220 --> 00:08:05,950 This one, OK, so this is my start point, this is my end point. 134 00:08:06,400 --> 00:08:09,510 OK, so basically I will apply to buy new search. 135 00:08:09,520 --> 00:08:14,830 So the brute force way for solving this question, what we have to do, we have to find the target value. 136 00:08:14,830 --> 00:08:16,840 So the brute force is basically a linear search. 137 00:08:17,230 --> 00:08:23,550 OK, so for linear search time and space, the time will be linear and space will be open. 138 00:08:23,680 --> 00:08:26,770 But I will solve this question with the help of binary search. 139 00:08:27,190 --> 00:08:30,050 Now let's see how we can solve this question with the help of binary search. 140 00:08:30,610 --> 00:08:32,039 So this is my start point. 141 00:08:32,740 --> 00:08:34,090 This is my end point. 142 00:08:34,840 --> 00:08:37,600 And what I will do, standard approach. 143 00:08:37,600 --> 00:08:38,830 I will find mid. 144 00:08:39,159 --> 00:08:41,620 What made mid will be start by two. 145 00:08:43,280 --> 00:08:47,310 OK, now made can lie here or we can lie here. 146 00:08:47,480 --> 00:08:50,080 OK, so maybe you can lie here. 147 00:08:51,230 --> 00:08:52,700 Made can also lie here. 148 00:08:53,730 --> 00:08:58,930 Now, first case, let's say it is in this part, OK, murders in this part. 149 00:08:59,250 --> 00:09:00,480 So how we can check. 150 00:09:01,480 --> 00:09:04,140 So this is, let's take it, case number one. 151 00:09:05,410 --> 00:09:07,660 OK, so our case number one. 152 00:09:08,940 --> 00:09:10,750 Miles length here. 153 00:09:11,310 --> 00:09:13,540 So how we will check what I will do. 154 00:09:13,560 --> 00:09:18,300 I will simply write if murder is less than end. 155 00:09:19,180 --> 00:09:21,180 OK, so I will simply write. 156 00:09:22,400 --> 00:09:23,840 If mythically. 157 00:09:25,410 --> 00:09:30,900 If it is less than Alef and that means it is lying ahead. 158 00:09:31,220 --> 00:09:33,120 OK, so in this sordid part. 159 00:09:34,630 --> 00:09:39,250 OK, and for lying here, what were the condition for me to be here? 160 00:09:39,280 --> 00:09:41,580 What were the conditions for the conditions to be very simple. 161 00:09:42,220 --> 00:09:48,140 So basically a officemate basically made will be greater than the start. 162 00:09:49,530 --> 00:09:52,690 OK, now let us consider this case. 163 00:09:54,390 --> 00:09:59,760 OK, so here, after we know where the middle is, we have a key value. 164 00:10:00,950 --> 00:10:07,670 So the key can be here or the key can be in the left hand side, so key can be in the right hand side, 165 00:10:07,670 --> 00:10:09,030 key can be in the left hand side. 166 00:10:09,050 --> 00:10:10,070 How do we decide? 167 00:10:11,000 --> 00:10:16,670 So I will separate Tofurky lying in the right hand side, four key lying in the attaches. 168 00:10:16,820 --> 00:10:21,680 So key should be between the middle value and between the end point. 169 00:10:22,340 --> 00:10:31,700 So inside this, if the key basically will be good then made and the key will be basically less than 170 00:10:31,700 --> 00:10:32,420 the end point. 171 00:10:32,450 --> 00:10:36,170 So basically key is lying here at this part in this region. 172 00:10:36,410 --> 00:10:39,500 Then what I will do, I will write start equals murder plus one. 173 00:10:40,990 --> 00:10:45,850 Now, in the early part, what can I do so the MD, so the Ghyslain basically in the left hand side, 174 00:10:46,090 --> 00:10:49,690 so I will right and equals minus one. 175 00:10:51,460 --> 00:10:54,130 OK, so this is our case number one. 176 00:10:55,230 --> 00:10:58,030 Now, let us consider case number two, basically this case. 177 00:10:58,050 --> 00:11:02,040 So this is our case, too, so is lying here. 178 00:11:03,180 --> 00:11:09,330 OK, so it is lying here now again, the key can be lie, the key can be found in the left hand side 179 00:11:09,330 --> 00:11:11,690 or the key can be found in the right hand side. 180 00:11:12,150 --> 00:11:17,370 So for to be present in this part, basically in the left hand side, the key should be greater than 181 00:11:17,370 --> 00:11:18,990 the start and less downward. 182 00:11:19,350 --> 00:11:20,520 OK, so. 183 00:11:21,650 --> 00:11:31,120 If what can I write here, so if the key is a good, then start and basically the key is less than read, 184 00:11:31,850 --> 00:11:32,720 then what will happen? 185 00:11:34,000 --> 00:11:38,240 At this point between the mid and the start, so what can I do? 186 00:11:38,260 --> 00:11:40,390 I will write an article similar to minus one. 187 00:11:41,910 --> 00:11:43,560 And the key will right? 188 00:11:43,770 --> 00:11:46,430 That's the key, will lie in the right hand side of the middle. 189 00:11:46,440 --> 00:11:47,490 So I will right. 190 00:11:48,390 --> 00:11:50,850 So I will write start mid plus one. 191 00:11:52,990 --> 00:11:54,970 OK, and the turkeys. 192 00:11:55,750 --> 00:12:00,550 So the turkeys is basically very simple, basically made equals, equals. 193 00:12:02,310 --> 00:12:05,990 In that case, I will simply return the index, so I will return with. 194 00:12:07,220 --> 00:12:11,420 OK, so I have to handle three cases, case three is very simple to handle. 195 00:12:11,420 --> 00:12:15,500 This is simple binary search and these are two special cases. 196 00:12:15,530 --> 00:12:15,890 OK. 197 00:12:17,450 --> 00:12:24,560 Our first problem is to find where metals lead can lie in this part or it can lie in this part, and 198 00:12:24,560 --> 00:12:28,820 with the help of these conditions, we can find out where it lies. 199 00:12:29,000 --> 00:12:30,620 OK, so one more time. 200 00:12:32,280 --> 00:12:34,170 Let's write this all clearly. 201 00:12:41,030 --> 00:12:43,460 So I'm drawing Bigram one more time, you, Dunklin. 202 00:12:46,300 --> 00:12:50,950 OK, so this is my start point and this is my end point. 203 00:12:51,500 --> 00:12:57,220 OK, so first of all, what I will do, I will find made point, which is Astarte percent right now, 204 00:12:57,220 --> 00:12:58,720 let's say, is Lakehead. 205 00:12:59,770 --> 00:13:01,610 Now to be lie in this part. 206 00:13:01,630 --> 00:13:07,840 So this is basically our let's say this is our case one and this is our case, too. 207 00:13:08,350 --> 00:13:10,450 So in case with with here. 208 00:13:11,990 --> 00:13:18,830 OK, so let us write about the cases like this one, and this is our case, too. 209 00:13:19,490 --> 00:13:22,380 So for me to be laying here, what is the condition? 210 00:13:22,940 --> 00:13:31,580 So basically made should be good, then start and for lying and for gays to murder should be less than 211 00:13:31,580 --> 00:13:31,880 end. 212 00:13:32,700 --> 00:13:34,210 OK, very simple. 213 00:13:34,790 --> 00:13:42,320 Now, now case when the queen can be present in this part or the geek can represent the right hand side. 214 00:13:42,890 --> 00:13:44,690 So for to be presented. 215 00:13:45,970 --> 00:13:50,860 The key should be good, then start and Key should be left handed, OK, so. 216 00:13:51,840 --> 00:14:02,910 If the key is to then start and the key is less than what I will do, so I will write and equals minus 217 00:14:02,910 --> 00:14:03,150 one. 218 00:14:04,360 --> 00:14:08,530 And what I will do, I will write start equals my plus one. 219 00:14:10,360 --> 00:14:11,030 Very simple. 220 00:14:11,500 --> 00:14:17,710 Now, let us consider case number two so she can be present in the right hand side of the world or she 221 00:14:17,710 --> 00:14:19,780 can represent the left hand side of the world. 222 00:14:20,050 --> 00:14:23,770 So what present for you to be present in the right hand side of the world? 223 00:14:24,010 --> 00:14:27,290 What is the condition for key lie between with and. 224 00:14:27,670 --> 00:14:28,180 So I will. 225 00:14:28,180 --> 00:14:28,490 Right. 226 00:14:28,840 --> 00:14:38,020 So if the key is good then made and the key is basically Lieutenant Leonski lies between them lies between 227 00:14:38,160 --> 00:14:39,360 midnight and end. 228 00:14:39,370 --> 00:14:42,190 So I will right start equals my plus one. 229 00:14:43,710 --> 00:14:48,450 And in the early part, it will lie in the left hand side, so I will write and equal to maybe minus 230 00:14:48,450 --> 00:14:48,660 one. 231 00:14:50,790 --> 00:14:58,230 And our third case is very simple, if murder is it close to key, then read, I will write, I will 232 00:14:58,230 --> 00:14:59,250 simply return with. 233 00:15:01,270 --> 00:15:05,890 OK, so now let us write the code if you understood the logic. 234 00:15:08,350 --> 00:15:15,820 So writing code is very straightforward, I will take two pointers, so start will be zero and obviously 235 00:15:16,330 --> 00:15:19,000 the end will be ignored, says minus one. 236 00:15:21,560 --> 00:15:28,010 OK, so again, our standard condition will start as less than articles end. 237 00:15:33,180 --> 00:15:35,390 So what I have to do, first of all, I will find. 238 00:15:35,910 --> 00:15:42,060 OK, so let us find out which is nothing but start plus and try to. 239 00:15:44,630 --> 00:15:51,410 Now, after finding the mud, so the very simple case, so if mud is equal to the given element. 240 00:15:52,630 --> 00:15:55,000 Then I'd have to return, I can simply return. 241 00:15:56,430 --> 00:16:00,670 OK, now let us go to the LS part, OK? 242 00:16:02,380 --> 00:16:05,440 We have to handle two cases, so let us first handle. 243 00:16:06,660 --> 00:16:07,780 This one, OK? 244 00:16:08,070 --> 00:16:13,700 Case one, civil case one, murders basically good, then start OK. 245 00:16:14,930 --> 00:16:17,480 So if aof start. 246 00:16:18,690 --> 00:16:19,530 It's basically. 247 00:16:20,910 --> 00:16:21,450 Than mid. 248 00:16:22,880 --> 00:16:24,050 Sudi A.M.. 249 00:16:26,710 --> 00:16:28,090 Now, I have two cases. 250 00:16:30,430 --> 00:16:38,170 So, Jason, I have to check for the key, and so this is case one and the case doing so Ghyslain between 251 00:16:38,170 --> 00:16:39,650 start and OK. 252 00:16:42,890 --> 00:16:43,970 So if. 253 00:16:46,490 --> 00:16:46,880 GI. 254 00:16:48,540 --> 00:16:50,550 It's basically get it and start. 255 00:16:54,430 --> 00:16:56,920 And the key is basically listin. 256 00:16:57,520 --> 00:16:57,900 OK. 257 00:17:00,260 --> 00:17:05,240 Then would have to do so, I have to search in the right hand side so and equals minus one. 258 00:17:08,359 --> 00:17:11,960 In the early part, I can write articles medicalising. 259 00:17:13,970 --> 00:17:19,280 OK, now we will do the similar, so in the elusive condition. 260 00:17:20,740 --> 00:17:21,790 So in the early part. 261 00:17:23,380 --> 00:17:29,710 So it's part means so in the old part, Minsky's Mayday's laying here, OK, ladies, line here. 262 00:17:30,490 --> 00:17:35,990 So I have to these two conditions, OK, the kids between the middle and the end point. 263 00:17:37,420 --> 00:17:39,790 So if the key is. 264 00:17:41,290 --> 00:17:42,460 He's lower than mid. 265 00:17:44,840 --> 00:17:47,390 And the key is basically listin and. 266 00:17:49,180 --> 00:17:53,770 Denki is laying in the right hand side, for starters, plus one. 267 00:17:55,010 --> 00:17:57,290 In the early part, Ghyslain organdy. 268 00:17:58,640 --> 00:18:01,270 Left hand side so and equals to minus one. 269 00:18:05,980 --> 00:18:07,390 OK, and finally. 270 00:18:08,790 --> 00:18:15,690 If this statement if the statement is not being executed, that means the gun element is the gun is 271 00:18:15,690 --> 00:18:18,390 not present inside the area, then I can return minus one. 272 00:18:22,470 --> 00:18:26,310 OK, so let us in our code and then we will try to submit our code. 273 00:18:30,060 --> 00:18:31,080 OK, so. 274 00:18:33,210 --> 00:18:35,260 So we have to read this explanation, OK? 275 00:18:36,280 --> 00:18:38,290 So right, this second condition also. 276 00:18:46,090 --> 00:18:47,170 Now it will work fine. 277 00:18:53,490 --> 00:18:55,020 OK, so let's it. 278 00:18:59,900 --> 00:19:06,190 OK, so our code is working fine, so just remember, you have to use the call operator, OK? 279 00:19:06,200 --> 00:19:08,710 You can try in and take one example to understand it better. 280 00:19:11,120 --> 00:19:17,810 Now of the time and the space complexity, so if you use if you are using linear search, so this is 281 00:19:17,810 --> 00:19:20,330 a very simple approach, time and space. 282 00:19:20,870 --> 00:19:27,200 Now, if you're using Binish search, so the time complexity is basically log often and the space complexity 283 00:19:27,200 --> 00:19:28,370 is basically order of one. 284 00:19:28,690 --> 00:19:30,730 OK, so let us revise. 285 00:19:31,220 --> 00:19:35,400 So the most important thing to understand this question is basically to understand the diagram. 286 00:19:35,470 --> 00:19:37,160 OK, so this will be the diagram. 287 00:19:39,260 --> 00:19:40,640 This is basically the diagram. 288 00:19:41,780 --> 00:19:43,370 OK, so this will be the diagram. 289 00:19:44,270 --> 00:19:47,770 OK, so this is basically the start and this is basically the end. 290 00:19:47,990 --> 00:19:49,580 So start will be good then end. 291 00:19:50,600 --> 00:19:56,270 OK, generally, so this is the diagram for an outdated sort today, and then you have to handle symbols 292 00:19:56,270 --> 00:19:59,360 in both cases, American life here, American life here. 293 00:19:59,630 --> 00:20:03,920 Now, after finding where the mud is lying, you have to find whether you have to call on the left hand 294 00:20:03,920 --> 00:20:06,450 side or do you have to call on the right hand side? 295 00:20:06,470 --> 00:20:10,310 Similarly, you have to call on the left hand side or you have to call on the right hand side. 296 00:20:10,460 --> 00:20:14,600 And that we can decide whether the key is lying here or whether. 297 00:20:14,870 --> 00:20:19,050 So if the key is lying here, then call on the left hand side, otherwise right then side. 298 00:20:19,250 --> 00:20:23,930 So if the key is lying here, then call in the right and say to the race, call in the left hand side. 299 00:20:24,290 --> 00:20:24,650 OK.