1 00:00:00,920 --> 00:00:01,620 Hi, everyone. 2 00:00:01,640 --> 00:00:09,230 So today we are going to solve this question, find the first and the last position of a given element 3 00:00:09,230 --> 00:00:10,180 in a sartorially. 4 00:00:10,770 --> 00:00:12,810 OK, so let us take example. 5 00:00:12,810 --> 00:00:15,560 Let us consider example and try to understand this question. 6 00:00:15,890 --> 00:00:18,200 OK, so this is basically our input. 7 00:00:18,440 --> 00:00:22,430 So input will be added and that it will be Assad today. 8 00:00:22,490 --> 00:00:30,430 OK, so input basically Assad today and we will be given a target element and we have to find this targeting. 9 00:00:30,440 --> 00:00:33,530 We have to find the first and the last position of this element. 10 00:00:33,620 --> 00:00:35,930 OK, so let us consider this example. 11 00:00:36,290 --> 00:00:38,140 So five is the target value. 12 00:00:38,540 --> 00:00:42,560 So what is the first position and what is the last position? 13 00:00:43,370 --> 00:00:44,720 OK, so the first position. 14 00:00:44,720 --> 00:00:46,220 So this is index zero. 15 00:00:46,220 --> 00:00:49,160 One, two, three, four, five. 16 00:00:49,370 --> 00:00:56,300 OK, so basically the first position is indexed to so first is two and the last is basically the next 17 00:00:56,300 --> 00:00:56,640 five. 18 00:00:56,930 --> 00:00:58,640 So last year and next five. 19 00:00:58,970 --> 00:01:01,170 OK, now let us consider this example. 20 00:01:01,190 --> 00:01:03,230 So the target value is basically seven. 21 00:01:04,040 --> 00:01:06,620 So the first position of seven is zero. 22 00:01:06,620 --> 00:01:10,550 One, two, three, four, five and six. 23 00:01:10,610 --> 00:01:14,870 OK, so first position is six and last position is also six. 24 00:01:15,800 --> 00:01:17,550 Now, let us consider this example. 25 00:01:17,600 --> 00:01:23,280 OK, so the target value is basically eight, so zero one, two, three and four. 26 00:01:23,690 --> 00:01:28,790 So basically the first position is three and the last position is basically food. 27 00:01:29,360 --> 00:01:31,160 Now, let us consider this example. 28 00:01:31,340 --> 00:01:37,770 OK, so the target value is basically six and we can see basically six is not present inside this area. 29 00:01:38,090 --> 00:01:42,260 So first position is minus one and last position is also minus one. 30 00:01:42,260 --> 00:01:44,660 Minus one basically means does not exist. 31 00:01:45,290 --> 00:01:50,390 OK, so this is our coalition and this coalition is basically present only told. 32 00:01:50,660 --> 00:01:53,690 OK, so this is the question that we are going to solve. 33 00:01:54,140 --> 00:01:57,560 OK, now let's see how we can solve this question. 34 00:01:58,430 --> 00:02:00,980 OK, so let's see how we can solve this question. 35 00:02:00,980 --> 00:02:03,290 So let us bright in on this example. 36 00:02:04,250 --> 00:02:05,990 OK, so what we will do. 37 00:02:08,070 --> 00:02:15,050 So suppose I have a target value and this target value is that it will exist inside the. 38 00:02:16,290 --> 00:02:19,870 And either it will not exist, there are two options. 39 00:02:19,920 --> 00:02:25,050 OK, so if it doesn't exist, then my answer would be minus one first point and last point, also minus 40 00:02:25,050 --> 00:02:25,200 one. 41 00:02:25,500 --> 00:02:28,230 Now, if it exists now, there are two options. 42 00:02:28,620 --> 00:02:35,940 It can be duplicates or they can be only one element or only one unique value. 43 00:02:37,500 --> 00:02:44,130 So since the area sorted, so basically the first the very brute force approach for solving this question 44 00:02:44,130 --> 00:02:45,300 is linear such. 45 00:02:46,910 --> 00:02:54,080 OK, so what we will do, we will simply iterate over the area and we will check whether the target 46 00:02:54,080 --> 00:02:55,070 exists or not. 47 00:02:55,250 --> 00:03:00,590 OK, so what do the time complexity for using the linear search so that time complexity will be linear. 48 00:03:00,800 --> 00:03:01,190 OK. 49 00:03:02,050 --> 00:03:04,030 And space complexity will be open. 50 00:03:04,060 --> 00:03:10,720 OK, so this is their time and this is the space, but the problem with linear is it does not consider 51 00:03:10,720 --> 00:03:12,730 the fact that the given area started. 52 00:03:13,320 --> 00:03:17,260 OK, so the given area is sorted since the governor is sorted. 53 00:03:17,290 --> 00:03:19,030 So we can apply binary search. 54 00:03:19,870 --> 00:03:21,340 We can apply binary search. 55 00:03:21,370 --> 00:03:24,080 OK, now let's see how we can apply by new search. 56 00:03:24,400 --> 00:03:28,330 So what Minnesota uses, for example, this is your already. 57 00:03:29,700 --> 00:03:32,730 Now, first, let us think about simple binary search. 58 00:03:32,990 --> 00:03:42,630 OK, so simple by necessity 2.0, start pointer and pointer, try to find the midpoint, which is basically 59 00:03:42,630 --> 00:03:43,340 a start plus. 60 00:03:43,350 --> 00:03:48,830 And why do now compare the midpoint with the target value. 61 00:03:49,410 --> 00:03:55,080 And if you find and if you find the midpoint, which is the target value, you can simply return the 62 00:03:55,080 --> 00:03:55,650 midpoint. 63 00:03:56,220 --> 00:03:59,040 OK, so this is basically a simple binary search. 64 00:03:59,340 --> 00:04:02,220 Now this question is basically a modification of binary search. 65 00:04:02,460 --> 00:04:03,920 OK, so what will happen? 66 00:04:03,930 --> 00:04:06,720 So if you let's say you want to find the first position. 67 00:04:07,540 --> 00:04:12,270 OK, so if you want to find the first portion, let us consider an example. 68 00:04:12,300 --> 00:04:16,279 So let's say there are some elements, then we have a target value. 69 00:04:17,010 --> 00:04:21,839 Then let's say again, we have target value again, we have target value again, we have target value 70 00:04:21,839 --> 00:04:25,920 and some more and some more elements inside the array. 71 00:04:26,010 --> 00:04:28,800 OK, so we have to find the first position. 72 00:04:28,800 --> 00:04:31,080 Basically, we have to find the index. 73 00:04:31,770 --> 00:04:34,570 OK, so we have to find the index at this point. 74 00:04:34,920 --> 00:04:36,480 So how we can solve this problem. 75 00:04:36,780 --> 00:04:42,380 So again, will take 2.8, let's say this is my starting point and let's say this is my end point. 76 00:04:42,390 --> 00:04:48,990 There again, we will find out the mid, which is and I think it will be simply start plus and by OK 77 00:04:49,170 --> 00:04:50,790 again, we will do the same step. 78 00:04:51,330 --> 00:04:53,140 We will compare mid and target. 79 00:04:53,160 --> 00:04:56,520 So I'm comparing within Target, let's say this is my mid. 80 00:04:56,760 --> 00:04:59,760 OK, so let's say this came out to be mid. 81 00:05:01,680 --> 00:05:07,200 Now, in the simple binary search, I will return from here, but this is the modification of my research. 82 00:05:07,230 --> 00:05:11,950 So what we will do so if this is made, I will store my answer here. 83 00:05:12,000 --> 00:05:14,290 OK, so I will temporarily stole my answer. 84 00:05:14,310 --> 00:05:16,230 So let's say I have another variable. 85 00:05:16,500 --> 00:05:20,450 So I'm suddenly close to the middle, which is basically the index. 86 00:05:20,460 --> 00:05:23,900 So I will store the index, but I will not return anything. 87 00:05:23,910 --> 00:05:26,280 OK, so I will not return anything here. 88 00:05:26,310 --> 00:05:31,860 What I will do, I will remove and from here and I will put end here, OK. 89 00:05:31,860 --> 00:05:34,830 And I will do one more operation and equals minus one. 90 00:05:35,520 --> 00:05:38,570 OK, since we have to find the first position. 91 00:05:39,510 --> 00:05:43,710 So obviously if I came here that means this can be our answer. 92 00:05:44,130 --> 00:05:46,210 OK, but we have to find the first portion. 93 00:05:46,230 --> 00:05:48,400 That means I have to consider the left part. 94 00:05:48,930 --> 00:05:51,270 OK, I have to search in the left part. 95 00:05:52,710 --> 00:05:55,960 OK, so I have to do this operation and the climate minus one. 96 00:05:56,520 --> 00:06:01,980 Now, if you want to find the last position, OK, consider this one example only. 97 00:06:02,460 --> 00:06:06,480 So you have some elements, then you have target value, then you have target value, then you have 98 00:06:06,480 --> 00:06:10,020 target value, then you have target value and similarly some more elements. 99 00:06:10,340 --> 00:06:16,680 OK, so suppose this is start and this is basically end and you came out with this one. 100 00:06:16,990 --> 00:06:22,140 OK, so again, what I will do, you will find out the method, which is nothing. 101 00:06:22,150 --> 00:06:25,770 It is basically start plus and bitou again. 102 00:06:25,770 --> 00:06:27,450 You will compare it with Target. 103 00:06:28,050 --> 00:06:34,440 So I am comparing what with I'm comparing like with Target and then also what you will do, you will 104 00:06:34,440 --> 00:06:35,320 store your answer. 105 00:06:35,340 --> 00:06:36,330 So answer the question. 106 00:06:37,530 --> 00:06:38,640 And one last thing. 107 00:06:39,030 --> 00:06:46,680 So since I have to find the last Oaklands, so basically the last Oaklands will be present at the right 108 00:06:46,680 --> 00:06:48,330 hand side of the mid value. 109 00:06:48,380 --> 00:06:52,260 OK, so what I will do, I will do start equals murder plus one. 110 00:06:54,660 --> 00:06:57,600 OK, now one thing, I am storing the answer. 111 00:06:58,500 --> 00:07:00,910 OK, so I am storing the answer basically. 112 00:07:01,810 --> 00:07:03,490 Suppose there does not exist. 113 00:07:03,510 --> 00:07:04,860 There is only one value. 114 00:07:04,920 --> 00:07:06,600 OK, so there is only one target value. 115 00:07:06,610 --> 00:07:07,820 There are not duplicates. 116 00:07:08,130 --> 00:07:10,060 So what will happen at this point. 117 00:07:10,080 --> 00:07:11,280 Suppose you are here. 118 00:07:11,850 --> 00:07:17,130 So basically you will store your answer in the variable answer and then you are searching in the right 119 00:07:17,130 --> 00:07:19,770 and say, OK, I'm searching in the right hand side. 120 00:07:19,770 --> 00:07:21,920 And obviously we have only one value. 121 00:07:22,020 --> 00:07:24,850 So in the right hand side we will not be able to find any value. 122 00:07:25,050 --> 00:07:29,430 So that's why I have stored my answer in a variable answer. 123 00:07:29,460 --> 00:07:30,600 And finally, what will do? 124 00:07:30,600 --> 00:07:31,710 We will return answer. 125 00:07:33,030 --> 00:07:38,730 When development and similarly, I hear I will return answer when my wife Lupin's. 126 00:07:39,060 --> 00:07:44,760 OK, so that's how I will be able to find the first and the last occurrence. 127 00:07:46,050 --> 00:07:50,990 OK, so now let us write the code for this, OK? 128 00:07:55,050 --> 00:07:56,490 So let us write the code. 129 00:07:58,800 --> 00:08:05,130 So you can implement yourself, but there is no need to implement a so let us basically implement the 130 00:08:05,130 --> 00:08:06,120 binary such approach. 131 00:08:06,150 --> 00:08:13,020 OK, so by search there will be an index, there will be integer because I Willetton Index, basically. 132 00:08:13,290 --> 00:08:17,990 OK, and let's say the name of the function is get first, get first position. 133 00:08:18,000 --> 00:08:20,100 OK, so get first. 134 00:08:22,570 --> 00:08:28,720 What it will take, so it will take basically a week Peres input and obviously our target value. 135 00:08:29,750 --> 00:08:34,580 So that bears input and it will take our target value. 136 00:08:37,440 --> 00:08:43,559 OK, so first, let us write the simple binary search approach so I have to take two point to start 137 00:08:43,559 --> 00:08:52,710 engines to start is basically zero and we have and pointer, which is basically a start size minus one. 138 00:08:54,520 --> 00:09:01,880 Then our standard by such gold, so while the start is less than our request to end, would have to 139 00:09:01,880 --> 00:09:03,800 rule, you have to find the midpoint. 140 00:09:04,150 --> 00:09:09,250 So my point is basically start plus and buy to what you can. 141 00:09:09,250 --> 00:09:09,620 Right. 142 00:09:10,270 --> 00:09:11,670 I have told you that another way. 143 00:09:11,680 --> 00:09:13,140 So that either way is very simple. 144 00:09:13,150 --> 00:09:17,710 So and plus start plus and minus start by doing OK. 145 00:09:18,070 --> 00:09:20,770 So this is basically same as start plus and by two. 146 00:09:25,260 --> 00:09:30,290 OK, so this one is better because in this case, in digital jihad, we did OK. 147 00:09:31,260 --> 00:09:35,390 So after calculating them, it would have to do I have to compare the mood of the target value. 148 00:09:35,430 --> 00:09:37,020 OK, so let's compare. 149 00:09:37,590 --> 00:09:45,270 So if basically Nimsoft murder equals equals target. 150 00:09:47,050 --> 00:09:52,280 It was staggered then what I have to do so in the original by such I will return it from here. 151 00:09:52,810 --> 00:09:57,430 OK, so first I am writing the original my new search, then I will modify the by search. 152 00:09:57,620 --> 00:09:59,620 OK, and the elusive part. 153 00:10:00,940 --> 00:10:01,810 So if. 154 00:10:03,050 --> 00:10:03,530 Mid. 155 00:10:05,210 --> 00:10:09,080 So if murder is basically less than target. 156 00:10:11,020 --> 00:10:17,590 Then what I have to do, so if the murders Lester Target, so what I have to do, I have to start Goldschmid 157 00:10:17,680 --> 00:10:20,830 plus one, so I have to search in the right hand side. 158 00:10:21,230 --> 00:10:23,740 OK, so we start Goldschmid plus one. 159 00:10:24,990 --> 00:10:30,270 And India, the part of what I will do, so I will write and equals minus one. 160 00:10:33,250 --> 00:10:40,220 OK, so this is our standard by Newswatch, now we have to modify our binary search and how we can modify. 161 00:10:40,600 --> 00:10:42,000 So what I have to do, I have to. 162 00:10:42,490 --> 00:10:49,600 So when I get the call condition for finding the first position, I think the first finding the first 163 00:10:49,600 --> 00:10:50,350 version I will do. 164 00:10:50,350 --> 00:10:51,770 And the ultimate minus one. 165 00:10:51,940 --> 00:10:54,280 OK, I have to search in the left hand side. 166 00:10:55,360 --> 00:10:58,150 I have to search in the left hand side for the first document. 167 00:10:59,050 --> 00:11:01,900 OK, so and I also need one variable answer. 168 00:11:02,020 --> 00:11:04,630 OK, so let's create a variable answer. 169 00:11:07,980 --> 00:11:11,890 So I have a variable answer, which is initially minus one. 170 00:11:12,760 --> 00:11:15,180 OK, now I will not return. 171 00:11:16,200 --> 00:11:17,960 OK, so this is the modification. 172 00:11:17,970 --> 00:11:18,900 I cannot return. 173 00:11:19,680 --> 00:11:21,680 I will first save my answer. 174 00:11:22,170 --> 00:11:24,360 So I'm saving my answer made. 175 00:11:24,660 --> 00:11:27,840 And then I have to search in the left hand side for the first position. 176 00:11:28,080 --> 00:11:30,120 So I will do an equal number to minus one. 177 00:11:31,200 --> 00:11:35,920 OK, so we have to search in the left hand side for the first version. 178 00:11:35,940 --> 00:11:39,210 OK, allergist's left hand side for the first position. 179 00:11:40,950 --> 00:11:46,620 And finally, what I will do so when the loop ends, I will return my answer, I will attend the first 180 00:11:46,620 --> 00:11:49,200 operation and now let us write the code for the. 181 00:11:50,680 --> 00:11:51,770 Last also. 182 00:11:51,820 --> 00:11:57,610 OK, so I'm writing the code, so get first, then the function will be get lost. 183 00:11:58,900 --> 00:12:05,680 Get lost position, it will also take no target and what will the condition so. 184 00:12:06,910 --> 00:12:12,910 The only difference will be so instead of searching the left hand side, I will search in the right 185 00:12:12,910 --> 00:12:14,860 hand side for the last position. 186 00:12:16,670 --> 00:12:19,250 So basically, I will start equals less one. 187 00:12:21,860 --> 00:12:23,820 I will start equals plus one. 188 00:12:23,890 --> 00:12:24,200 OK. 189 00:12:25,290 --> 00:12:29,380 Now, let us call these functions body functions from here. 190 00:12:29,820 --> 00:12:33,280 So what I have to return, you can see I have to return a vector. 191 00:12:33,330 --> 00:12:35,750 OK, so Vector will contain two values. 192 00:12:36,750 --> 00:12:41,760 The first operation and the last portion you can see I have to return a vector of two elements. 193 00:12:41,760 --> 00:12:43,730 First position and the last version. 194 00:12:44,490 --> 00:12:44,850 OK. 195 00:12:46,690 --> 00:12:48,640 So let us create a vector. 196 00:12:50,630 --> 00:12:58,280 So, Victor, of integers, let's say, why it has to be a size two and let us initialize with minus 197 00:12:58,280 --> 00:12:58,520 one. 198 00:12:58,740 --> 00:13:02,030 OK, so I'm initializing our vector with minus one. 199 00:13:02,870 --> 00:13:04,460 Now, let us call this function. 200 00:13:04,670 --> 00:13:05,390 Get first. 201 00:13:07,010 --> 00:13:07,370 OK. 202 00:13:08,490 --> 00:13:16,350 So I'm calling the function get first, so in less time storing the indexing variable first, so I have 203 00:13:16,350 --> 00:13:16,770 a function. 204 00:13:18,070 --> 00:13:23,620 Get first, it will take vectorized input and it will take the target as input. 205 00:13:26,420 --> 00:13:27,710 OK, so. 206 00:13:29,170 --> 00:13:31,330 If first equals equals minus one. 207 00:13:34,130 --> 00:13:36,000 So basically, element does not exist. 208 00:13:36,020 --> 00:13:40,400 OK, so in this case, if the target is six, you can see the element will not be present. 209 00:13:40,430 --> 00:13:41,810 So our answer will be minus one. 210 00:13:41,870 --> 00:13:43,790 OK, so first is minus one. 211 00:13:44,120 --> 00:13:45,890 That means the first politician is minus one. 212 00:13:45,890 --> 00:13:47,650 That means the element does not exist. 213 00:13:47,930 --> 00:13:49,540 So you can simply return later. 214 00:13:49,760 --> 00:13:50,810 You can simply return. 215 00:13:51,980 --> 00:13:57,800 OK, otherwise what you have to do, we will call, we will get to the last position. 216 00:13:59,070 --> 00:14:01,200 So last is basically get lost. 217 00:14:02,530 --> 00:14:03,670 It will also take. 218 00:14:05,240 --> 00:14:08,060 That bears input and obviously the target value. 219 00:14:11,210 --> 00:14:19,670 OK, and finally, I will put I will update my so zero to perdition will contain the first. 220 00:14:21,030 --> 00:14:29,800 And the first petition will contain the last and finally I can return my answer so that be OK. 221 00:14:30,000 --> 00:14:32,830 So I hope I have done everything correctly. 222 00:14:32,850 --> 00:14:36,570 Now let us now accord and then we will try to submit our code, OK? 223 00:14:40,280 --> 00:14:42,470 OK, so now let us try to submit our good. 224 00:14:46,270 --> 00:14:48,850 OK, so our goal is working fine. 225 00:14:49,180 --> 00:14:52,260 OK, now let's see how it is working. 226 00:15:07,000 --> 00:15:12,580 OK, so I have a function get first position, so it will take a week, but as important, it will also 227 00:15:12,580 --> 00:15:13,740 take the target value. 228 00:15:14,050 --> 00:15:15,840 And then this is the standard code. 229 00:15:15,850 --> 00:15:17,440 I will take this dart pointer. 230 00:15:17,440 --> 00:15:18,790 I will take the pointer. 231 00:15:19,060 --> 00:15:24,630 OK, so what I am doing here, so I will I am taking the start pointer, which is the next zero. 232 00:15:24,640 --> 00:15:27,760 I am taking the end point which is index and minus one. 233 00:15:28,060 --> 00:15:31,110 Then I'm calculating which is a start position by two. 234 00:15:31,450 --> 00:15:33,790 Now I'm comparing with the target value. 235 00:15:34,040 --> 00:15:41,780 OK, so after comparing it with the target value to this target and let's say this is our mode, OK, 236 00:15:41,800 --> 00:15:44,410 so let's target then what I'm doing. 237 00:15:44,410 --> 00:15:47,620 So I'm taking a variable answer, which is initially minus one. 238 00:15:47,650 --> 00:15:50,630 Minus one means basically the element does not exist. 239 00:15:50,650 --> 00:15:58,360 OK, so answer is basically, let's say this index is two, so answer will store two and then what I 240 00:15:58,360 --> 00:16:06,160 am doing, I am doing and equals minus one so and remove and so and will be here so and equals basically 241 00:16:06,160 --> 00:16:10,810 with minus one and then the binary search will be applied in this part. 242 00:16:11,050 --> 00:16:13,900 So in this part we will apply the binary search. 243 00:16:14,390 --> 00:16:17,480 OK, and suppose we have only one target value. 244 00:16:17,500 --> 00:16:22,630 So in this part we will not be able to find any target value and this value will end. 245 00:16:22,900 --> 00:16:24,790 And then I am returning my answer. 246 00:16:25,220 --> 00:16:26,740 OK, so I return to. 247 00:16:27,630 --> 00:16:31,240 Now, suppose if there is a target value present in the left hand side. 248 00:16:31,290 --> 00:16:35,340 OK, so let's say this is a target, target, target, then what will happen? 249 00:16:35,700 --> 00:16:38,640 So I will to my mother, basically this one. 250 00:16:40,080 --> 00:16:41,730 OK, let's say this is the. 251 00:16:42,240 --> 00:16:48,400 Then what I'm going to do here is so I will update my answer again to this Medders basically index. 252 00:16:48,490 --> 00:16:49,600 But what I will do. 253 00:16:49,620 --> 00:16:51,400 So this answer very well will be updated. 254 00:16:51,450 --> 00:16:57,330 It will become one and then I will do an equal number minus one so and will be here and then I will 255 00:16:57,330 --> 00:16:58,920 apply the bonus on this part. 256 00:16:59,510 --> 00:17:05,250 OK, basically the only modification that we have to do with the bin searches do not return directly, 257 00:17:05,280 --> 00:17:12,859 OK, after finding the target value, do not return directly searching the left hand side, searching 258 00:17:12,880 --> 00:17:18,540 the left hand side and similarly for finding the last position, OK, for finding the last position, 259 00:17:18,540 --> 00:17:19,829 do not return directly. 260 00:17:19,859 --> 00:17:25,349 So if the method is basically cultural target value, then do not return anything. 261 00:17:25,720 --> 00:17:30,780 OK, first store the temporary answer and then search on the right hand side. 262 00:17:31,530 --> 00:17:35,400 And for searching the return site, I have to do start equiptment plus one. 263 00:17:35,400 --> 00:17:38,810 OK, search on the right hand side for the last value. 264 00:17:40,230 --> 00:17:41,800 So basically do not directly return. 265 00:17:41,820 --> 00:17:45,900 OK, so what do we the time and the space complexity since we are using binary search. 266 00:17:45,900 --> 00:17:52,380 So the time complexity is basically logoff in and our space complexity is basically outdraw one. 267 00:17:53,390 --> 00:17:56,610 OK, so this space complexity is basically order of one. 268 00:17:59,500 --> 00:18:05,500 Now, in this part where we are calling the function, so what I'm doing here is so basically. 269 00:18:06,730 --> 00:18:10,850 So basically, at this point, what will happen, but this land will lose, it will create a vector 270 00:18:10,900 --> 00:18:14,960 with the Navy and Vector can store only two elements. 271 00:18:15,280 --> 00:18:17,580 So the first and they are initialized with minus one. 272 00:18:17,590 --> 00:18:19,330 So it is minus one and minus one. 273 00:18:19,810 --> 00:18:22,630 OK, and then I'm calling our function. 274 00:18:22,630 --> 00:18:23,260 Get first. 275 00:18:23,590 --> 00:18:24,490 So get first. 276 00:18:24,670 --> 00:18:25,510 Will I get it done. 277 00:18:25,510 --> 00:18:25,990 Minus one. 278 00:18:25,990 --> 00:18:30,670 That means the element does not exist or it will return the first position of the target value. 279 00:18:31,780 --> 00:18:37,660 So if it is returning minus one, ok, if it is returning minus one, that means the dagger does not 280 00:18:37,660 --> 00:18:38,130 exist. 281 00:18:38,140 --> 00:18:42,130 So there is no need to call in this function because it will also return minus one. 282 00:18:42,600 --> 00:18:47,390 So that's why I am returning V from here and which is basically minus one and minus one. 283 00:18:47,710 --> 00:18:52,990 OK, so if this is not the case, that means the target element is better inside the array. 284 00:18:53,260 --> 00:18:56,110 And then I'm getting I'm calling the function get lost. 285 00:18:56,110 --> 00:18:58,000 It will return me the last position. 286 00:18:58,820 --> 00:19:02,650 It will return with the last position and then I am updating my vector. 287 00:19:02,720 --> 00:19:05,890 OK, so this will contain this is V of zero. 288 00:19:06,050 --> 00:19:07,860 So this is indexical, this is the next one. 289 00:19:08,080 --> 00:19:13,030 So this will contain the first position and this will contain the last position. 290 00:19:13,030 --> 00:19:18,430 And then I am returning V OK vs basically vector and you can see the return type of the function, this 291 00:19:18,700 --> 00:19:19,240 vector. 292 00:19:19,480 --> 00:19:21,000 So that's why I am returning vector. 293 00:19:22,200 --> 00:19:29,790 OK, so what you can do here is so you can see this function, get lost function and get first function, 294 00:19:30,120 --> 00:19:35,110 so the only difference between these two function is this line and the consumer minus one. 295 00:19:35,140 --> 00:19:37,570 And here I am doing start a quantum replacement. 296 00:19:37,980 --> 00:19:41,650 OK, so this is the only difference between these two functions. 297 00:19:42,060 --> 00:19:45,190 So what we can do is write a general code. 298 00:19:45,810 --> 00:19:46,920 So let me show you first. 299 00:19:46,920 --> 00:19:48,120 What I'm going to do here is. 300 00:19:49,150 --> 00:19:53,890 So let us come and let us copy this part and then I will come and dirtball dysfunctions. 301 00:19:54,960 --> 00:19:58,320 And then let me show you how we can write this code in a better way. 302 00:19:59,330 --> 00:19:59,750 OK. 303 00:20:02,760 --> 00:20:09,590 So this is basically the gold and I want one function and that one function will return me the first 304 00:20:09,600 --> 00:20:10,910 position and the last position. 305 00:20:11,250 --> 00:20:13,500 So let's say the name of the function is good index. 306 00:20:14,160 --> 00:20:19,890 OK, so it will take one more argument and that argument is basically a boolean value. 307 00:20:20,250 --> 00:20:23,670 Basically search for first or let's get first. 308 00:20:26,120 --> 00:20:26,870 Get first. 309 00:20:27,080 --> 00:20:35,270 OK, so and let's say by default, this value is so if you know about the default value, you can ride 310 00:20:35,280 --> 00:20:35,760 through here. 311 00:20:35,780 --> 00:20:38,850 But let's say you do not know about default arguments. 312 00:20:39,560 --> 00:20:44,960 So what we can do here is so instead of calling on end of minus one, so I will check first. 313 00:20:46,890 --> 00:20:51,660 So I have to write if condition here, so what I'm going to do if. 314 00:20:53,400 --> 00:20:57,000 Get first, basically this variable, so you've got first is true. 315 00:20:59,720 --> 00:21:05,120 If great first is true, what I'm going to do, I will do and equals minus one. 316 00:21:08,620 --> 00:21:10,750 Symbol in the old part. 317 00:21:12,700 --> 00:21:15,580 What I will do, so I will do that article, smart person. 318 00:21:39,760 --> 00:21:44,960 OK, so search on the left hand side for first position. 319 00:21:45,520 --> 00:21:52,810 Now, if the first is false, what I will do, I will search on the right hand side for last position. 320 00:21:53,970 --> 00:21:58,860 And instead of calling these two different function, I have one function only then able to function 321 00:21:58,860 --> 00:21:59,820 is to get index. 322 00:22:00,930 --> 00:22:02,680 And I will start arguing. 323 00:22:02,820 --> 00:22:10,920 OK, so if I want to find the first valuate, I will pass, I will pass through and here, since I do 324 00:22:10,920 --> 00:22:13,590 not want to find the first value, I will pass false. 325 00:22:14,160 --> 00:22:15,940 OK, I want to find the lost value. 326 00:22:16,500 --> 00:22:19,780 So as you can see here, we have only one function get indexed. 327 00:22:19,810 --> 00:22:22,080 OK, so I have to change the name of the function here. 328 00:22:22,800 --> 00:22:28,020 The name of the function is get indexed, it is taking vector, it is taking a target value and it is 329 00:22:28,020 --> 00:22:30,330 taking a third argument which will be true or false. 330 00:22:30,600 --> 00:22:33,270 OK, so that argument is basically true or false. 331 00:22:33,540 --> 00:22:37,260 So if the third argument is basically true, what I will do, I will do. 332 00:22:37,260 --> 00:22:41,400 And a classmate of mine, this one, because we have to find the first portion. 333 00:22:41,640 --> 00:22:46,770 And if the third argument is false, basically you can see if the argument is false, we have to find 334 00:22:46,800 --> 00:22:47,760 the last position. 335 00:22:48,270 --> 00:22:51,300 So we're finding the last person I will do start equals my plus one. 336 00:22:51,840 --> 00:22:54,240 OK, so let's try to separate alcalde. 337 00:22:57,340 --> 00:22:59,060 OK, so compilation of. 338 00:23:06,690 --> 00:23:08,820 OK, so there will be when Brexiteer. 339 00:23:13,140 --> 00:23:14,130 No, legitimate. 340 00:23:17,680 --> 00:23:19,720 OK, so our goal is working fine. 341 00:23:19,870 --> 00:23:24,520 OK, so with the help of this third argument, we do not need to write to functions. 342 00:23:24,520 --> 00:23:29,530 So here we have written two functions and the only defense is basically this line between these two 343 00:23:29,530 --> 00:23:30,040 functions. 344 00:23:30,340 --> 00:23:34,600 So to avoid writing two functions, what we can do, we can pass a third argument. 345 00:23:35,170 --> 00:23:39,310 And with the help of third argument, we can write a health condition and then. 346 00:23:40,380 --> 00:23:44,040 We can't go like this, OK, so this is a better way to write the code. 347 00:23:45,100 --> 00:23:47,360 OK, so what is the time in the space complexity? 348 00:23:48,190 --> 00:23:54,910 So basically, since we are using the brain research time, complexity is basically log in and the space 349 00:23:54,910 --> 00:23:57,040 complexity, we are not using any extra space. 350 00:23:57,050 --> 00:23:58,230 So it is our draughtsman. 351 00:23:58,330 --> 00:24:03,430 OK, so this is basically binary search for linear search. 352 00:24:03,430 --> 00:24:07,750 The time complexity was when and this vast complexity was 01. 353 00:24:07,970 --> 00:24:10,300 OK, so this is linear search. 354 00:24:11,780 --> 00:24:17,580 OK, so if you have any doubt in this question or do you have any doubt in the court, you can ask me, 355 00:24:17,630 --> 00:24:19,220 OK, thank you.