1 00:00:00,550 --> 00:00:01,510 Welcome back. 2 00:00:01,510 --> 00:00:06,820 Let's now go ahead and implement the solution that we discussed to find the range of the target value 3 00:00:06,820 --> 00:00:08,410 which is given to us in the array. 4 00:00:08,440 --> 00:00:11,830 Now first let's go ahead and implement this in the recursive manner. 5 00:00:11,830 --> 00:00:13,540 For this we will need a function. 6 00:00:13,540 --> 00:00:16,270 Let's call it search for range. 7 00:00:17,860 --> 00:00:18,730 Recursive. 8 00:00:18,730 --> 00:00:25,000 And this function is going to take in the array which is given to us, and also the target value. 9 00:00:26,520 --> 00:00:34,800 Now inside the function, let's say const range is equal to an array with the values minus one and minus 10 00:00:34,800 --> 00:00:35,370 one. 11 00:00:35,370 --> 00:00:37,890 And we are going to call two functions. 12 00:00:37,890 --> 00:00:39,960 So these are going to be recursive functions. 13 00:00:39,960 --> 00:00:42,720 So let's call one find left extreme. 14 00:00:44,830 --> 00:00:49,840 And this function is going to take in the array the target value and the range. 15 00:00:50,320 --> 00:00:53,830 And it's going to modify the range if it finds the target value. 16 00:00:53,830 --> 00:00:54,100 All right. 17 00:00:54,100 --> 00:00:55,270 So it will modify this. 18 00:00:55,270 --> 00:00:58,780 And then let's have one more function let's say find right extreme. 19 00:01:01,510 --> 00:01:05,830 And this function also is going to take in the array and the target value and the range. 20 00:01:05,830 --> 00:01:11,350 And it will modify the right extreme which is this value over here in the array of this in the range 21 00:01:11,350 --> 00:01:11,710 array. 22 00:01:11,710 --> 00:01:14,950 And then finally we will just return the range. 23 00:01:15,430 --> 00:01:16,840 So this is how we will implement it. 24 00:01:16,840 --> 00:01:18,880 So let's go ahead and write these functions. 25 00:01:18,880 --> 00:01:21,580 So let's start with find left extreme. 26 00:01:23,370 --> 00:01:30,390 Now this function, as we have seen, is going to take in the array the target value and the range. 27 00:01:31,830 --> 00:01:35,520 Now once inside the function let's first write the base case. 28 00:01:35,520 --> 00:01:37,470 So this is going to be a recursive function. 29 00:01:37,470 --> 00:01:37,740 All right. 30 00:01:37,740 --> 00:01:41,880 So we will call this function again if required inside the function. 31 00:01:41,880 --> 00:01:45,600 Now the base case is going to be if left is greater than right right. 32 00:01:45,600 --> 00:01:52,140 So if that is the case then we can know that the target value is not there in the array which is given 33 00:01:52,140 --> 00:01:52,680 to us. 34 00:01:52,680 --> 00:01:54,630 And we can just return in that case. 35 00:01:54,630 --> 00:01:55,560 So we will just return. 36 00:01:55,560 --> 00:01:58,410 If left is greater than right we will just return. 37 00:01:58,410 --> 00:02:00,660 Now if this is not the case let's proceed. 38 00:02:00,660 --> 00:02:02,670 So we will calculate the middle value. 39 00:02:02,670 --> 00:02:05,280 So middle is going to be math dot floor. 40 00:02:07,230 --> 00:02:08,730 Left plus right. 41 00:02:13,090 --> 00:02:14,440 Divided by two. 42 00:02:14,830 --> 00:02:16,540 So this is going to be the middle index. 43 00:02:16,570 --> 00:02:22,480 Now let's go ahead and check if the value in the array at this particular index is equal to the target. 44 00:02:22,480 --> 00:02:25,270 So if array at middle. 45 00:02:26,580 --> 00:02:28,140 Is equal to target. 46 00:02:28,990 --> 00:02:31,390 If this is the case, then we proceed. 47 00:02:31,390 --> 00:02:31,750 All right. 48 00:02:31,750 --> 00:02:37,420 So as long as this is not achieved, as long as we have not re, uh, found the target value at the 49 00:02:37,420 --> 00:02:40,150 middle case, it's going to be same as binary search. 50 00:02:40,150 --> 00:02:40,420 Right. 51 00:02:40,420 --> 00:02:43,030 So over here if that if let's just continue. 52 00:02:43,030 --> 00:02:45,130 So we will come back and fill this over here. 53 00:02:45,130 --> 00:02:49,210 Now if the value at the middle index is not equal to target. 54 00:02:49,210 --> 00:02:53,710 So we are just going to check is target less than the value or greater than the value. 55 00:02:53,710 --> 00:02:55,810 So if target is less than array at middle. 56 00:02:55,810 --> 00:02:59,500 In that case we have to call this function again recursively. 57 00:03:00,300 --> 00:03:02,550 But we are going to look at the left part, right. 58 00:03:02,550 --> 00:03:06,630 So we are going to pass the function the parameters array target. 59 00:03:07,640 --> 00:03:10,880 Range, and then we'll have to change the left and right index. 60 00:03:10,880 --> 00:03:13,460 So over here also we'll have those right. 61 00:03:13,460 --> 00:03:15,290 So we'll have left over here as well. 62 00:03:15,290 --> 00:03:16,790 So let's initialize it to zero. 63 00:03:16,790 --> 00:03:19,280 So if it's not passed it will take the value zero. 64 00:03:19,280 --> 00:03:21,080 So we don't need to modify it over here. 65 00:03:21,080 --> 00:03:24,800 And then right is going to be array dot length. 66 00:03:27,060 --> 00:03:30,060 Minus one, so if it's not passed, it will just take this value. 67 00:03:30,060 --> 00:03:31,680 So we don't need to modify it over here. 68 00:03:31,680 --> 00:03:36,720 But in this case we have seen that target is less than the value at the middle index. 69 00:03:36,720 --> 00:03:38,970 So we have to look only in the left part. 70 00:03:38,970 --> 00:03:41,820 So we are going to change the value of right. 71 00:03:41,820 --> 00:03:42,090 All right. 72 00:03:42,090 --> 00:03:44,730 So the value of right is going to be middle minus one. 73 00:03:44,730 --> 00:03:45,780 So let's go ahead. 74 00:03:45,780 --> 00:03:47,250 So left is not changing. 75 00:03:47,250 --> 00:03:48,600 So left is as it is. 76 00:03:48,600 --> 00:03:51,060 And then right is going to be middle minus one. 77 00:03:51,060 --> 00:03:53,910 Because we only want to look towards the left of middle. 78 00:03:53,910 --> 00:03:59,970 Now if this is also not the case that is if right middle is not equal to target and right middle and 79 00:03:59,970 --> 00:04:04,230 target is not less than right middle, that means target is greater than right middle right. 80 00:04:04,230 --> 00:04:08,760 So if that is the case again we will recursively call find left extreme. 81 00:04:08,760 --> 00:04:12,660 And then we will pass the parameters array target range. 82 00:04:13,230 --> 00:04:16,020 And then we only want to look towards the right of the middle. 83 00:04:16,020 --> 00:04:18,570 So we are going to change left to middle plus one. 84 00:04:18,570 --> 00:04:21,120 The parameter left is going to be middle plus one. 85 00:04:21,120 --> 00:04:23,100 And then right does not change. 86 00:04:23,100 --> 00:04:23,520 All right. 87 00:04:23,520 --> 00:04:24,990 So this is how the function works. 88 00:04:24,990 --> 00:04:27,390 Now let's go ahead and complete this part over here. 89 00:04:27,390 --> 00:04:32,580 Now if we have found the value that that is right middle is equal to target. 90 00:04:32,580 --> 00:04:36,120 In this case we have to check first if middle is equal to zero. 91 00:04:36,120 --> 00:04:39,930 So if middle is equal to zero then we cannot go towards the left right. 92 00:04:39,930 --> 00:04:43,140 So that means that we have found the left extreme. 93 00:04:43,140 --> 00:04:47,790 And we can say range at index zero is going to be middle or zero. 94 00:04:47,790 --> 00:04:48,000 Right. 95 00:04:48,000 --> 00:04:49,350 So I am just writing zero. 96 00:04:49,350 --> 00:04:51,120 So at this point middle is equal to zero. 97 00:04:51,120 --> 00:04:52,440 So I can write either way. 98 00:04:52,440 --> 00:04:58,980 Now if this is not the case that is if middle is not equal to zero then we have to check if the element 99 00:04:58,980 --> 00:05:04,890 to the towards the left, that is, if the element at index middle minus one is equal to the target. 100 00:05:04,890 --> 00:05:05,610 So let's check that. 101 00:05:05,610 --> 00:05:09,480 So else if array at middle minus one. 102 00:05:10,470 --> 00:05:17,190 If this is equal to target, then we have not yet found our left extreme right, so we have to continue. 103 00:05:17,190 --> 00:05:22,110 If this is the case, then we have to continue calling the function recursively. 104 00:05:22,110 --> 00:05:24,300 So we'll say find left extreme. 105 00:05:24,300 --> 00:05:26,370 And then we have to look towards the left part. 106 00:05:26,370 --> 00:05:29,190 So let's pass the parameters array target. 107 00:05:29,990 --> 00:05:33,350 The range and we want to look towards the left part. 108 00:05:33,350 --> 00:05:38,210 So left does not change and right becomes middle minus one. 109 00:05:40,020 --> 00:05:41,250 Right now. 110 00:05:41,250 --> 00:05:47,340 If this is not the case, that is, if the element towards the left of the middle middle index is not 111 00:05:47,340 --> 00:05:51,090 equal to target, then we have found our left extreme right. 112 00:05:51,090 --> 00:05:52,650 So if this is not the case. 113 00:05:52,650 --> 00:05:53,400 So let's write. 114 00:05:53,400 --> 00:05:56,760 So else we have found our left extreme. 115 00:05:56,760 --> 00:06:02,160 And we can say range at zero is going to be equal to middle. 116 00:06:02,520 --> 00:06:05,790 Because whatever is left to this index is not equal to the target. 117 00:06:05,790 --> 00:06:07,320 So we have found the left extreme. 118 00:06:07,320 --> 00:06:07,770 All right. 119 00:06:07,770 --> 00:06:10,650 So this is the find left extreme function. 120 00:06:10,650 --> 00:06:14,220 Now let's go ahead and write the find right extreme function as well. 121 00:06:15,670 --> 00:06:17,140 So here we say const. 122 00:06:19,700 --> 00:06:20,840 Find right extreme. 123 00:06:20,840 --> 00:06:26,120 And this function is going to be pretty similar to the previous previous function with some modifications. 124 00:06:26,120 --> 00:06:30,260 So again this function also takes in array target range. 125 00:06:30,260 --> 00:06:33,200 And this also will take the pointers left and right. 126 00:06:33,200 --> 00:06:38,120 So left is equal to zero and right is equal to array dot length. 127 00:06:40,000 --> 00:06:41,020 Minus one. 128 00:06:42,340 --> 00:06:45,730 Now, once inside the function again, we start with the base case. 129 00:06:45,730 --> 00:06:49,570 So the base case is if left is greater than right so if left. 130 00:06:50,920 --> 00:06:53,410 Greater than right now. 131 00:06:53,410 --> 00:06:55,240 In this case, we can just return. 132 00:06:55,570 --> 00:06:55,840 All right. 133 00:06:55,840 --> 00:06:56,890 So that's the base case. 134 00:06:56,890 --> 00:06:59,020 Now if this is not the case we proceed. 135 00:06:59,020 --> 00:07:04,150 So we'll say const middle is equal to math dot floor. 136 00:07:05,750 --> 00:07:07,160 Left plus right. 137 00:07:08,080 --> 00:07:09,340 Divided by two. 138 00:07:09,370 --> 00:07:11,080 So we find the middle index. 139 00:07:11,110 --> 00:07:16,420 Now we are going to check if array at middle is equal to target. 140 00:07:17,770 --> 00:07:19,270 So let's just keep this over here. 141 00:07:19,300 --> 00:07:23,020 Now if it is not equal then it's just simple binary search. 142 00:07:23,020 --> 00:07:23,260 All right. 143 00:07:23,260 --> 00:07:24,400 So we proceed. 144 00:07:24,400 --> 00:07:28,060 So else if target is less than array at middle. 145 00:07:28,060 --> 00:07:31,150 If this is the case then we look towards the left part right. 146 00:07:31,150 --> 00:07:35,410 So we can recursively call the same function find right extreme. 147 00:07:36,870 --> 00:07:40,260 And we're going to pass the parameters array target. 148 00:07:41,380 --> 00:07:47,080 Range and we want to look towards the left part because array is less than the middle value. 149 00:07:47,080 --> 00:07:52,360 So left does not change and right becomes middle minus one. 150 00:07:53,980 --> 00:07:58,630 Now if this is not the case, that means target is greater than array at middle. 151 00:07:58,630 --> 00:08:04,210 So if target is greater than array at middle, we are again going to call the same function recursively. 152 00:08:04,240 --> 00:08:09,910 We pass the parameters, but we want to look towards the right part because target is greater than array 153 00:08:09,910 --> 00:08:10,450 at middle. 154 00:08:10,450 --> 00:08:11,920 So array target. 155 00:08:12,070 --> 00:08:13,870 Then we pass the range. 156 00:08:13,870 --> 00:08:18,850 And because we want to look towards the right, left is going to change to middle plus one. 157 00:08:18,850 --> 00:08:20,680 And then right does not change. 158 00:08:21,580 --> 00:08:22,120 All right. 159 00:08:22,150 --> 00:08:24,010 Now let's come and finish this part over here. 160 00:08:24,010 --> 00:08:29,890 If array at middle is equal to target we are first going to check if middle is the right most index 161 00:08:29,890 --> 00:08:31,750 of the given array which is given to us. 162 00:08:31,750 --> 00:08:36,970 So if middle is equal to array dot length minus one. 163 00:08:41,300 --> 00:08:45,110 So that means we are at the right most index and we cannot go any further. 164 00:08:45,110 --> 00:08:45,380 Right? 165 00:08:45,380 --> 00:08:45,740 Right. 166 00:08:45,740 --> 00:08:48,140 That means we have found the right index. 167 00:08:48,140 --> 00:08:54,140 So in this case we can say range at one is equal to middle. 168 00:08:55,000 --> 00:08:57,550 Because middle is equal to right length minus one. 169 00:08:57,550 --> 00:09:02,470 So we can say either range at one is equal to middle or range at one is equal to array dot length minus 170 00:09:02,470 --> 00:09:02,830 one. 171 00:09:02,830 --> 00:09:03,850 Now let's proceed. 172 00:09:03,850 --> 00:09:11,050 If this is not the case then we check if the next element that is at the element at middle plus one 173 00:09:11,050 --> 00:09:13,930 index is equal to the target, so else. 174 00:09:15,350 --> 00:09:21,260 If target is equal to array at middle plus one. 175 00:09:22,380 --> 00:09:28,800 Then we have to call the function recursively and look towards the right to find right extreme, and 176 00:09:28,800 --> 00:09:33,120 we pass the parameters array target range. 177 00:09:33,300 --> 00:09:35,370 And we want to look towards the right. 178 00:09:35,370 --> 00:09:42,000 So left is going to change to middle plus one and right is remaining as it is right. 179 00:09:42,000 --> 00:09:47,850 Now if this is not the case that is if the next element is not equal to target, then we have found 180 00:09:47,850 --> 00:09:54,210 the right extreme and we can say range at one right, which is the which is denoting the right extreme 181 00:09:54,210 --> 00:09:55,770 is equal to middle. 182 00:09:57,510 --> 00:09:57,990 All right. 183 00:09:57,990 --> 00:09:59,490 So that brings us to the end. 184 00:09:59,490 --> 00:10:01,830 So we have done we are done with writing the function. 185 00:10:01,830 --> 00:10:05,490 So we have written find right extreme function which is recursively called. 186 00:10:05,490 --> 00:10:08,010 And we have written the find left extreme function. 187 00:10:08,010 --> 00:10:09,840 And we are calling both of these over here. 188 00:10:09,840 --> 00:10:13,110 And it will change these values of the range array. 189 00:10:13,110 --> 00:10:15,420 And then finally we are just returning the range array. 190 00:10:15,420 --> 00:10:17,550 So let's go ahead and test our function. 191 00:10:17,550 --> 00:10:19,710 So we have this function let's call it. 192 00:10:22,280 --> 00:10:24,230 And let's pass in an array. 193 00:10:24,230 --> 00:10:27,500 So again the first parameter is the array and then the target value. 194 00:10:27,530 --> 00:10:29,030 So let's go ahead and pass in an array. 195 00:10:29,030 --> 00:10:33,410 Let's say one comma one comma 2223 and four. 196 00:10:33,410 --> 00:10:35,900 And let's say we are looking for the value two. 197 00:10:36,050 --> 00:10:40,970 Now our expectation is that it should return the indices of this and this right. 198 00:10:40,970 --> 00:10:42,170 So this is zero one. 199 00:10:42,170 --> 00:10:44,450 This is two this is index two three and four. 200 00:10:44,450 --> 00:10:46,760 So two comma four is what we expect. 201 00:10:46,760 --> 00:10:50,150 So let's go ahead and run the function and see the output. 202 00:10:51,160 --> 00:10:51,430 All right. 203 00:10:51,430 --> 00:10:52,390 So we have an error. 204 00:10:52,390 --> 00:10:54,250 So let's just check it left is not defined. 205 00:10:54,250 --> 00:10:56,740 So somewhere instead of left I have written left. 206 00:10:56,740 --> 00:10:57,970 So let's see that. 207 00:10:57,970 --> 00:10:58,270 All right. 208 00:10:58,270 --> 00:11:00,400 So it's that over here it should be left. 209 00:11:00,880 --> 00:11:02,380 Now let's again run this. 210 00:11:02,860 --> 00:11:03,220 All right. 211 00:11:03,220 --> 00:11:05,950 So we are getting our output two comma four. 212 00:11:05,950 --> 00:11:07,990 So this is our index 2012. 213 00:11:07,990 --> 00:11:08,890 Yes that's correct. 214 00:11:08,890 --> 00:11:10,210 And this is index four. 215 00:11:10,210 --> 00:11:11,050 So this is correct. 216 00:11:11,050 --> 00:11:12,490 So we are getting the right answer. 217 00:11:12,490 --> 00:11:15,010 Now what if we were looking for one. 218 00:11:15,040 --> 00:11:16,090 Let's see. 219 00:11:16,880 --> 00:11:19,190 So we'll get zero comma, one zero and one. 220 00:11:19,190 --> 00:11:19,820 That's correct. 221 00:11:19,820 --> 00:11:21,140 Which is these two. 222 00:11:21,140 --> 00:11:21,320 Right. 223 00:11:21,320 --> 00:11:22,280 These two indices. 224 00:11:22,280 --> 00:11:24,680 What if we were looking for the value for. 225 00:11:26,590 --> 00:11:28,810 We get six comma six which is this index. 226 00:11:28,810 --> 00:11:29,170 Right. 227 00:11:29,170 --> 00:11:33,130 So this is 012345 and six which is correct. 228 00:11:33,130 --> 00:11:35,830 And what if we were looking for let's say five. 229 00:11:35,860 --> 00:11:38,140 It should give minus one comma minus one. 230 00:11:38,140 --> 00:11:38,320 Right. 231 00:11:38,320 --> 00:11:40,420 Because five is not there in the array. 232 00:11:40,420 --> 00:11:41,590 And yes that's correct. 233 00:11:41,590 --> 00:11:43,450 So this function is working correct. 234 00:11:43,450 --> 00:11:45,940 So let's go ahead and see how this is working. 235 00:11:45,940 --> 00:11:49,270 Now let's say we are calling the search for range rect function. 236 00:11:49,270 --> 00:11:51,100 This is the array that we are passing to it. 237 00:11:51,100 --> 00:11:53,080 And the target value is equal to two. 238 00:11:53,110 --> 00:11:55,150 So let's now see what's happening. 239 00:11:55,150 --> 00:11:56,410 So we are over here. 240 00:11:56,410 --> 00:12:00,070 And range at this point is minus one comma minus one. 241 00:12:00,070 --> 00:12:05,380 And then we call the find left extreme function the array the target value and the range is passed to 242 00:12:05,380 --> 00:12:05,680 it. 243 00:12:05,680 --> 00:12:06,280 All right. 244 00:12:06,280 --> 00:12:07,330 So we are over here. 245 00:12:07,600 --> 00:12:10,180 And at this point left is equal to zero. 246 00:12:10,180 --> 00:12:13,420 And right is equal to array dot length minus one. 247 00:12:13,420 --> 00:12:17,800 So let me just trace the call stack over here so that we can understand this better. 248 00:12:17,800 --> 00:12:18,070 All right. 249 00:12:18,070 --> 00:12:20,710 Because this is going to be a recursive solution right. 250 00:12:20,710 --> 00:12:26,050 So at this point left is equal to zero and right is equal to array dot length minus one. 251 00:12:26,050 --> 00:12:28,600 The length over here is 34567. 252 00:12:28,600 --> 00:12:30,670 So seven minus one is equal to six. 253 00:12:30,670 --> 00:12:31,960 So right is equal to six. 254 00:12:31,960 --> 00:12:32,500 All right. 255 00:12:32,500 --> 00:12:34,570 Now is left greater than right. 256 00:12:34,570 --> 00:12:37,240 No right because left is zero and right is equal to six. 257 00:12:37,240 --> 00:12:42,610 So we come over here we calculate the middle value which is zero plus six divided by two which is equal 258 00:12:42,610 --> 00:12:43,330 to three. 259 00:12:43,330 --> 00:12:46,510 And then we are checking if array at middle is equal to target. 260 00:12:46,510 --> 00:12:52,420 So let me write the indices over here 012345 and six. 261 00:12:52,420 --> 00:12:54,100 So these are the indices over here. 262 00:12:54,580 --> 00:12:58,540 And you can see that yes array at index three is two right. 263 00:12:58,540 --> 00:12:59,980 So it's equal to two. 264 00:13:00,010 --> 00:13:01,420 So we come over here. 265 00:13:01,420 --> 00:13:03,460 Now we are checking if middle is equal to zero. 266 00:13:03,460 --> 00:13:04,600 No middle is equal to three. 267 00:13:04,600 --> 00:13:04,780 Right. 268 00:13:04,780 --> 00:13:05,980 So we don't go further. 269 00:13:05,980 --> 00:13:07,030 We come over here. 270 00:13:07,030 --> 00:13:12,130 We are checking if the previous value that is array at middle minus one is equal to target. 271 00:13:12,130 --> 00:13:13,930 So this is middle minus one. 272 00:13:13,930 --> 00:13:16,270 So we see that it's equal to the target two. 273 00:13:16,300 --> 00:13:17,590 So yes it's true. 274 00:13:17,590 --> 00:13:20,530 So we recursively call the find left extreme function. 275 00:13:20,530 --> 00:13:26,020 Again at this point left is going to be zero but right is going to be middle minus one which is two. 276 00:13:26,020 --> 00:13:27,610 Right three minus one is equal to two. 277 00:13:27,640 --> 00:13:28,810 So let's write that over here. 278 00:13:28,810 --> 00:13:33,280 We are calling the function again at this time left is zero and right is equal to two. 279 00:13:33,310 --> 00:13:35,290 Now let's clear this up. 280 00:13:36,650 --> 00:13:40,730 So we are again inside this function over here and left is equal to zero. 281 00:13:40,730 --> 00:13:42,200 Right is equal to two. 282 00:13:42,200 --> 00:13:44,780 And we see that zero greater than two. 283 00:13:44,780 --> 00:13:45,470 That's false. 284 00:13:45,590 --> 00:13:46,670 So we don't return. 285 00:13:46,670 --> 00:13:52,070 We come over here and we calculate middle which is zero plus two by two which is equal to one. 286 00:13:52,070 --> 00:13:53,480 So middle is equal to one. 287 00:13:53,480 --> 00:13:56,450 And now we are going to check if right middle is equal to target. 288 00:13:56,450 --> 00:13:57,410 No that's not true. 289 00:13:57,410 --> 00:13:57,680 Right. 290 00:13:57,680 --> 00:14:00,530 So one over here is not equal to the target two. 291 00:14:00,560 --> 00:14:02,510 So we come over here. 292 00:14:02,510 --> 00:14:04,730 Now is the target less than right. 293 00:14:04,730 --> 00:14:05,030 Middle. 294 00:14:05,030 --> 00:14:05,300 No. 295 00:14:05,300 --> 00:14:05,570 Right. 296 00:14:05,570 --> 00:14:08,780 Because target is two and right middle is equal to one. 297 00:14:08,780 --> 00:14:12,560 So we come over here and we call the function again recursively. 298 00:14:12,560 --> 00:14:15,680 And at this time we are going to make left to be middle. 299 00:14:15,680 --> 00:14:17,600 Plus one middle is equal to one right. 300 00:14:17,600 --> 00:14:18,860 So this is going to be two. 301 00:14:18,890 --> 00:14:20,420 So left is going to be two. 302 00:14:20,420 --> 00:14:22,880 And right is right itself which is two. 303 00:14:22,880 --> 00:14:25,310 So we are calling the function with two comma two. 304 00:14:25,310 --> 00:14:25,790 All right. 305 00:14:25,790 --> 00:14:27,800 So let's again come over here. 306 00:14:30,370 --> 00:14:37,180 Now we are again over here and you can see that left is two, right is also two and middle will be two, 307 00:14:37,180 --> 00:14:38,110 middle will be two. 308 00:14:38,110 --> 00:14:41,110 And we see that right middle is equal to target. 309 00:14:41,110 --> 00:14:42,310 So this is truthy. 310 00:14:42,340 --> 00:14:43,060 We come inside. 311 00:14:43,060 --> 00:14:44,320 Middle is not equal to zero. 312 00:14:44,320 --> 00:14:47,590 And we see that the previous value is not equal to target right. 313 00:14:47,590 --> 00:14:51,430 So therefore we can say that range at zero is equal to middle. 314 00:14:51,430 --> 00:14:52,810 So we are going to change this. 315 00:14:52,810 --> 00:14:54,100 This is range at zero right. 316 00:14:54,100 --> 00:14:57,040 This is going to be changed to middle which is equal to two. 317 00:14:57,070 --> 00:14:58,600 So that's how we get two over here. 318 00:14:58,600 --> 00:15:01,330 So this call over here will just complete right. 319 00:15:01,330 --> 00:15:03,880 So this will be just a recursive call over here. 320 00:15:04,420 --> 00:15:05,950 Uh I think it was part of this right. 321 00:15:05,950 --> 00:15:08,320 So once this is over it will just finish. 322 00:15:08,320 --> 00:15:10,990 It will just return and this call will just expire. 323 00:15:10,990 --> 00:15:15,520 Similarly, this call also will just finish wherever we came, wherever we did this call. 324 00:15:15,520 --> 00:15:15,820 Right. 325 00:15:15,820 --> 00:15:18,340 So it will finish once this is over. 326 00:15:18,340 --> 00:15:21,730 This call also is just going to finish because we are not returning anything. 327 00:15:21,730 --> 00:15:24,820 So this will also come finish and it will come out of the call stack. 328 00:15:24,820 --> 00:15:28,150 Similarly this also will come out of the call stack and we are done right. 329 00:15:28,150 --> 00:15:31,870 So in this way we will find the left extreme to be equal to two. 330 00:15:31,870 --> 00:15:34,420 And we get two comma minus one at this point. 331 00:15:34,420 --> 00:15:39,760 So let's just change this over here we have two comma minus one at the current moment the range. 332 00:15:39,760 --> 00:15:43,720 So again let's take a look at the main function. 333 00:15:43,720 --> 00:15:46,090 So let's clear this up. 334 00:15:50,550 --> 00:15:52,950 All right, so we are done with this call. 335 00:15:52,950 --> 00:15:54,960 Now we are going to call this find X right. 336 00:15:54,960 --> 00:15:55,440 Extreme. 337 00:15:55,440 --> 00:15:55,830 All right. 338 00:15:55,830 --> 00:15:57,750 So let's go to that function. 339 00:15:57,870 --> 00:15:59,880 And again we are calling the function. 340 00:15:59,880 --> 00:16:02,730 And we are not passing the left and the right. 341 00:16:02,730 --> 00:16:04,290 So left is going to be zero. 342 00:16:04,290 --> 00:16:07,800 And right is going to be array dot length minus one. 343 00:16:07,800 --> 00:16:10,110 So we know the length over here is seven. 344 00:16:10,110 --> 00:16:11,910 So that's going to be six right. 345 00:16:11,910 --> 00:16:12,780 Is going to be six. 346 00:16:12,780 --> 00:16:13,860 Left is zero. 347 00:16:13,860 --> 00:16:14,730 So let's. 348 00:16:15,460 --> 00:16:16,390 Trace that over here. 349 00:16:16,390 --> 00:16:19,900 So we have the call with zero and six. 350 00:16:20,550 --> 00:16:24,930 And then once inside this we check this left is not greater than right. 351 00:16:24,930 --> 00:16:29,190 So we come over here we calculate middle to be three and then array at three. 352 00:16:29,370 --> 00:16:31,200 Array at three is equal to the target. 353 00:16:31,200 --> 00:16:32,220 We have seen that over here. 354 00:16:32,220 --> 00:16:33,390 So we come inside. 355 00:16:33,390 --> 00:16:35,580 Middle is not equal to array dot length minus one. 356 00:16:35,580 --> 00:16:37,050 Right middle is equal to three. 357 00:16:37,050 --> 00:16:40,380 So we come over here and is the next value equal to two. 358 00:16:40,380 --> 00:16:41,700 That's what we are checking over here. 359 00:16:41,700 --> 00:16:43,410 We see that yes that is true. 360 00:16:43,410 --> 00:16:43,620 Right. 361 00:16:43,620 --> 00:16:47,970 So yes because of that we are going to make another recursive call over here. 362 00:16:47,970 --> 00:16:53,490 So let me just write this in red and we'll keep it over here so that we can see what happens once it 363 00:16:53,490 --> 00:16:54,120 returns. 364 00:16:54,120 --> 00:16:58,170 So at this point left is going to be middle plus one which is four. 365 00:16:58,170 --> 00:16:58,500 All right. 366 00:16:58,500 --> 00:17:00,900 So left is four and right is going to be six. 367 00:17:00,900 --> 00:17:01,860 And we make this call. 368 00:17:01,860 --> 00:17:03,480 We are again inside the function. 369 00:17:03,480 --> 00:17:04,050 All right. 370 00:17:04,080 --> 00:17:06,000 Now left is not greater than right. 371 00:17:06,000 --> 00:17:08,730 So we calculate middle which is four plus six is ten. 372 00:17:08,730 --> 00:17:10,320 Ten by two is equal to five. 373 00:17:10,320 --> 00:17:12,090 So middle is equal to five. 374 00:17:12,090 --> 00:17:16,260 Now mid array at five is not equal to target right. 375 00:17:16,260 --> 00:17:17,340 So it's not equal. 376 00:17:17,340 --> 00:17:20,610 So we come over here is target less than array at five. 377 00:17:20,760 --> 00:17:21,240 Yes. 378 00:17:21,240 --> 00:17:23,190 Target is less than array at five. 379 00:17:23,190 --> 00:17:25,980 So we are calling the function recursively over here. 380 00:17:25,980 --> 00:17:28,920 So at this point left is going to be as it is. 381 00:17:28,920 --> 00:17:30,180 So left is four itself. 382 00:17:30,180 --> 00:17:32,280 But right is going to be middle minus one. 383 00:17:32,280 --> 00:17:33,120 Middle is five. 384 00:17:33,120 --> 00:17:35,850 So right is going to be four itself five minus one is four. 385 00:17:35,850 --> 00:17:39,360 So we are having this recursive four call with four comma four. 386 00:17:40,240 --> 00:17:40,570 Again. 387 00:17:40,570 --> 00:17:41,590 We are inside over here. 388 00:17:41,590 --> 00:17:42,220 Now. 389 00:17:42,220 --> 00:17:46,810 At this point, middle also is going to be equal to four because that's four plus four by two. 390 00:17:46,810 --> 00:17:50,170 And we are checking whether array at four is equal to target. 391 00:17:50,170 --> 00:17:52,120 So we see yes that's the case. 392 00:17:52,120 --> 00:17:53,740 Array at four is equal to target. 393 00:17:53,740 --> 00:17:57,610 Now over here we are checking if the next element is equal to target. 394 00:17:57,610 --> 00:17:58,960 So middle plus one. 395 00:17:58,960 --> 00:17:59,950 That's this one over here. 396 00:17:59,950 --> 00:18:01,600 And we see it's not equal right. 397 00:18:01,600 --> 00:18:02,890 So it's not equal. 398 00:18:02,890 --> 00:18:07,780 So we come over here and we said range at one is equal to middle which is four. 399 00:18:07,780 --> 00:18:10,060 So we are going to change this value to four. 400 00:18:10,180 --> 00:18:10,570 Right. 401 00:18:10,570 --> 00:18:12,580 So that's how we get two comma four. 402 00:18:12,820 --> 00:18:15,490 In this way we have found the range. 403 00:18:15,490 --> 00:18:18,190 And then this will just expire and this will expire. 404 00:18:18,190 --> 00:18:19,960 And finally this also will expire. 405 00:18:19,960 --> 00:18:22,240 So this is how we are finding the range. 406 00:18:22,240 --> 00:18:22,720 All right. 407 00:18:22,720 --> 00:18:26,830 So let's take a quick look at the space and time complexity of this solution. 408 00:18:26,830 --> 00:18:33,640 So the time complexity of this solution is going to be O of log n right. 409 00:18:34,410 --> 00:18:39,120 Again, we could write two into log n because we're doing it two times over here, but then two is a 410 00:18:39,120 --> 00:18:40,710 constant so we can avoid it. 411 00:18:40,710 --> 00:18:41,070 All right. 412 00:18:41,070 --> 00:18:43,620 So the time complexity is O of log n. 413 00:18:43,620 --> 00:18:45,420 What about the space complexity. 414 00:18:45,420 --> 00:18:51,120 Now the space complexity is also O of log n because this is the recursive solution. 415 00:18:51,120 --> 00:18:54,240 And we will be using space on the call stack. 416 00:18:54,240 --> 00:18:59,640 So each time the maximum space used in the call stack will be of the order of log n. 417 00:18:59,640 --> 00:19:02,520 So over here also we may use log n space. 418 00:19:02,520 --> 00:19:04,860 And over here also we may use O of log in space. 419 00:19:04,860 --> 00:19:07,740 So the space complexity is going to be O of log n. 420 00:19:07,740 --> 00:19:12,150 And again we cannot say it's two into log n because this is at a time right. 421 00:19:12,150 --> 00:19:15,060 So we we want space used in the call stack at a time. 422 00:19:15,060 --> 00:19:17,880 So this this will just return and it will just expire. 423 00:19:17,880 --> 00:19:18,150 Right. 424 00:19:18,150 --> 00:19:19,410 And then we come over here. 425 00:19:19,410 --> 00:19:21,930 So the space complexity is O of log n.