1 00:00:00,000 --> 00:00:00,870 2 00:00:00,870 --> 00:00:04,152 SPEAKER 1: This is the first problem that we're going to be working on. 3 00:00:04,152 --> 00:00:04,860 I'll read it out. 4 00:00:04,860 --> 00:00:07,530 "Let's define a rotated array as assorted array 5 00:00:07,530 --> 00:00:11,640 where the numbers have all been rotated to the right some number of places, 6 00:00:11,640 --> 00:00:14,310 with numbers wrapping around when they reach the end." 7 00:00:14,310 --> 00:00:18,210 For instance, if you've got the array 1, 2, 3, 4, 5 and you rotate that three 8 00:00:18,210 --> 00:00:21,960 times, you're going to get 3, 4, 5, 1, 2. 9 00:00:21,960 --> 00:00:24,840 The problem here, is given a rotated array, 10 00:00:24,840 --> 00:00:27,915 find the number of times it was rotated. 11 00:00:27,915 --> 00:00:28,790 SPEAKER 2: All right. 12 00:00:28,790 --> 00:00:29,540 Well, hi, Tommy. 13 00:00:29,540 --> 00:00:30,290 How are you doing? 14 00:00:30,290 --> 00:00:30,890 I'm Connor. 15 00:00:30,890 --> 00:00:31,220 SPEAKER 1: Good. 16 00:00:31,220 --> 00:00:32,262 Nice to meet you, Connor. 17 00:00:32,262 --> 00:00:33,137 How's your day going? 18 00:00:33,137 --> 00:00:34,554 SPEAKER 2: It's going pretty well. 19 00:00:34,554 --> 00:00:35,160 And yours? 20 00:00:35,160 --> 00:00:35,480 SPEAKER 1: Awesome. 21 00:00:35,480 --> 00:00:36,140 Not too bad. 22 00:00:36,140 --> 00:00:38,490 It's pretty sunny out here in San Francisco, 23 00:00:38,490 --> 00:00:40,790 which doesn't happen too often. 24 00:00:40,790 --> 00:00:41,790 SPEAKER 2: That's great. 25 00:00:41,790 --> 00:00:45,330 Yeah, it's pretty warm out here for October in Cambridge. 26 00:00:45,330 --> 00:00:46,710 SPEAKER 1: Nice. 27 00:00:46,710 --> 00:00:49,000 All right, well, thanks for taking the time. 28 00:00:49,000 --> 00:00:51,495 Let's jump right into the question. 29 00:00:51,495 --> 00:00:52,620 You've got the Replit open. 30 00:00:52,620 --> 00:00:53,220 That's great. 31 00:00:53,220 --> 00:00:55,470 Notice that you've selected Python there. 32 00:00:55,470 --> 00:00:57,703 Is that the language that you want to use for this? 33 00:00:57,703 --> 00:00:58,620 SPEAKER 2: Yes, it is. 34 00:00:58,620 --> 00:00:59,412 SPEAKER 1: Perfect. 35 00:00:59,412 --> 00:01:02,550 That works for me. 36 00:01:02,550 --> 00:01:05,190 Here's the question that I'd like you to solve. 37 00:01:05,190 --> 00:01:08,460 "Let's define a rotated array as a sorted array 38 00:01:08,460 --> 00:01:12,540 where the numbers have all been rotated to the right some number of places, 39 00:01:12,540 --> 00:01:15,420 with numbers wrapping around when they reach the end." 40 00:01:15,420 --> 00:01:18,450 For instance, if I give you the input 1, 2, 3, 4, 5, 41 00:01:18,450 --> 00:01:21,170 you should return back 3, since-- 42 00:01:21,170 --> 00:01:22,920 or, sorry, when I rotate that three times, 43 00:01:22,920 --> 00:01:30,610 you should return back 3, basically, as you've written in the comment there. 44 00:01:30,610 --> 00:01:33,860 That's the question that I'd like you to solve. 45 00:01:33,860 --> 00:01:35,060 SPEAKER 2: OK, yeah. 46 00:01:35,060 --> 00:01:36,380 That sounds good. 47 00:01:36,380 --> 00:01:40,250 I'll start out by asking some clarifying questions, if that sounds good to you. 48 00:01:40,250 --> 00:01:41,342 SPEAKER 1: Yeah. 49 00:01:41,342 --> 00:01:44,300 SPEAKER 2: Just to make sure, it does say "given a rotated array" here. 50 00:01:44,300 --> 00:01:47,390 I just want to clarify that something like this right 51 00:01:47,390 --> 00:01:49,950 here would be our input. 52 00:01:49,950 --> 00:01:52,820 So I don't get this original array at all, 53 00:01:52,820 --> 00:01:54,710 I just get the rotated array as input? 54 00:01:54,710 --> 00:01:56,730 SPEAKER 1: Yep, that's right. 55 00:01:56,730 --> 00:01:57,720 SPEAKER 2: All right. 56 00:01:57,720 --> 00:02:04,170 And then my other clarifying question is, in this one, 57 00:02:04,170 --> 00:02:06,570 all of these are consecutive integers-- 58 00:02:06,570 --> 00:02:09,060 1, 2, 3, 4, 5 all right next to each other. 59 00:02:09,060 --> 00:02:11,910 Can I assume that that will be the case, or might there 60 00:02:11,910 --> 00:02:19,943 be a case where my original array is, like, 1, 3, 4, 7, 10? 61 00:02:19,943 --> 00:02:20,610 SPEAKER 1: Yeah. 62 00:02:20,610 --> 00:02:21,360 That could exist. 63 00:02:21,360 --> 00:02:24,910 They're not necessarily consecutive, but they are sorted. 64 00:02:24,910 --> 00:02:25,540 SPEAKER 2: OK. 65 00:02:25,540 --> 00:02:29,050 Yeah, that's good to know. 66 00:02:29,050 --> 00:02:34,180 In that case, let me just look at a couple of examples, 67 00:02:34,180 --> 00:02:38,500 just so I can see if we can start to see a pattern here. 68 00:02:38,500 --> 00:02:43,990 We see, when we get this first example, we want that to map to 3, 69 00:02:43,990 --> 00:02:47,680 because we're rotating that one three times. 70 00:02:47,680 --> 00:02:51,830 Let me see, if I were to rotate that one more time, 71 00:02:51,830 --> 00:02:58,060 then it would look like 2, 3, 4, 5, 1. 72 00:02:58,060 --> 00:03:02,320 That would be as if I had rotated it four times. 73 00:03:02,320 --> 00:03:05,440 And then I'll try some ones with different numbers. 74 00:03:05,440 --> 00:03:12,820 If my original array has some different numbers in it, 75 00:03:12,820 --> 00:03:19,630 a rotated one might look like 6, 8, 12, 1, 3. 76 00:03:19,630 --> 00:03:25,570 In this case, we would have rotated it-- 77 00:03:25,570 --> 00:03:28,450 1 would have been the original one. 78 00:03:28,450 --> 00:03:30,740 We've rotated it 1, 2, 3 times. 79 00:03:30,740 --> 00:03:35,140 So we would also want this one to return 3. 80 00:03:35,140 --> 00:03:42,560 And then just one more kind of edge-ish case is, if it's not sorted at all, 81 00:03:42,560 --> 00:03:46,480 I'm assuming that we would want to say that that was rotated zero times. 82 00:03:46,480 --> 00:03:49,150 SPEAKER 1: Yes, that's right. 83 00:03:49,150 --> 00:03:52,180 SPEAKER 2: Just to check in, do all of those cases seem good to you? 84 00:03:52,180 --> 00:03:52,847 SPEAKER 1: Yeah. 85 00:03:52,847 --> 00:03:55,085 Nothing else you'll probably run into here. 86 00:03:55,085 --> 00:03:55,960 SPEAKER 2: All right. 87 00:03:55,960 --> 00:03:57,400 Great. 88 00:03:57,400 --> 00:04:00,220 In that case, let me go ahead and run through looking for patterns. 89 00:04:00,220 --> 00:04:03,460 I can see just how I would figure this out, 90 00:04:03,460 --> 00:04:07,720 if I was looking through this as a human, is I would go to the first one-- 91 00:04:07,720 --> 00:04:11,800 and I guess the important thing I'm looking for is, all of these numbers 92 00:04:11,800 --> 00:04:13,000 are increasing. 93 00:04:13,000 --> 00:04:17,029 And I want to look for the first time that they decrease, 94 00:04:17,029 --> 00:04:19,120 so they start going down. 95 00:04:19,120 --> 00:04:22,180 In this case, I go to 0. 96 00:04:22,180 --> 00:04:23,020 I go to 1. 97 00:04:23,020 --> 00:04:23,920 It's increasing. 98 00:04:23,920 --> 00:04:24,640 I go to 2. 99 00:04:24,640 --> 00:04:25,660 It's increasing. 100 00:04:25,660 --> 00:04:30,860 And then when I get to element 3, it's decreasing, 101 00:04:30,860 --> 00:04:34,810 which means it's rotated three times. 102 00:04:34,810 --> 00:04:37,480 And then just to verify that, I'll go through this one. 103 00:04:37,480 --> 00:04:39,820 In this one, I start at element 0. 104 00:04:39,820 --> 00:04:41,080 Then 1. 105 00:04:41,080 --> 00:04:42,100 It's still increasing. 106 00:04:42,100 --> 00:04:43,120 2, still increasing. 107 00:04:43,120 --> 00:04:44,240 3, still increasing. 108 00:04:44,240 --> 00:04:47,380 But at 4, it decreases again. 109 00:04:47,380 --> 00:04:50,770 I think that is a pretty good pattern to use there, 110 00:04:50,770 --> 00:04:55,610 is that when we get to an index, when it starts decreasing, 111 00:04:55,610 --> 00:04:57,670 that's the index that we want to return. 112 00:04:57,670 --> 00:04:58,360 SPEAKER 1: Yeah. 113 00:04:58,360 --> 00:04:59,897 That looks exactly right to me. 114 00:04:59,897 --> 00:05:02,980 Yeah, that point where it goes from increasing to decreasing is the index. 115 00:05:02,980 --> 00:05:05,705 That tells you the number of times it's been rotated. 116 00:05:05,705 --> 00:05:06,580 SPEAKER 2: All right. 117 00:05:06,580 --> 00:05:07,080 Perfect. 118 00:05:07,080 --> 00:05:08,890 In that case, I think I'll go into writing 119 00:05:08,890 --> 00:05:10,432 some code if that sounds good to you. 120 00:05:10,432 --> 00:05:11,830 SPEAKER 1: Yeah, let's do that. 121 00:05:11,830 --> 00:05:14,350 SPEAKER 2: All right. 122 00:05:14,350 --> 00:05:17,110 I'll go ahead and define a function here. 123 00:05:17,110 --> 00:05:21,573 I guess I'll just say get_rotate_number. 124 00:05:21,573 --> 00:05:22,240 SPEAKER 1: Sure. 125 00:05:22,240 --> 00:05:24,150 Sounds good. 126 00:05:24,150 --> 00:05:28,952 SPEAKER 2: And it's going to take in this array. 127 00:05:28,952 --> 00:05:30,660 Ah, that looks like it might be reserved. 128 00:05:30,660 --> 00:05:34,490 So I'll take in a list ls. 129 00:05:34,490 --> 00:05:40,100 And now, I want to go through all of the elements in ls. 130 00:05:40,100 --> 00:05:41,880 And the index is important here. 131 00:05:41,880 --> 00:05:47,160 So I guess I'll go ahead and say, for i in range ls. 132 00:05:47,160 --> 00:05:49,940 And now, what I want to do is, for each i-- 133 00:05:49,940 --> 00:05:51,950 when I'm here, i is 2. 134 00:05:51,950 --> 00:05:57,200 I want to compare it to the one before that and see if it's less than that. 135 00:05:57,200 --> 00:06:00,080 Let me-- I guess I would say something like, 136 00:06:00,080 --> 00:06:08,120 if ls bracket i is less than ls bracket i minus 1-- 137 00:06:08,120 --> 00:06:12,680 we're saying, if my current element is less than the element 138 00:06:12,680 --> 00:06:16,820 before that, then I would go ahead and-- 139 00:06:16,820 --> 00:06:19,340 I know that that's the place that I want to stop. 140 00:06:19,340 --> 00:06:23,570 So I can go ahead and say, return i. 141 00:06:23,570 --> 00:06:27,950 And now, looking at this special case here where nothing happens, 142 00:06:27,950 --> 00:06:32,060 I guess I would go through this entire list and never get to that point. 143 00:06:32,060 --> 00:06:35,460 I guess, if I finish this whole thing-- 144 00:06:35,460 --> 00:06:40,340 so I don't find any point where an element is less than its predecessor-- 145 00:06:40,340 --> 00:06:42,650 I'm going to go ahead and return 0, since I know 146 00:06:42,650 --> 00:06:47,450 that the list is not rotated at all. 147 00:06:47,450 --> 00:06:50,000 Now, just as a sanity check, I'm going to go through this 148 00:06:50,000 --> 00:06:53,660 with this first example here. 149 00:06:53,660 --> 00:06:57,200 Acting as the computer, I take in ls, which is this list I've highlighted. 150 00:06:57,200 --> 00:07:00,860 And then I go ahead and say, for i in range ls-- 151 00:07:00,860 --> 00:07:02,930 that's going to start me off at 0. 152 00:07:02,930 --> 00:07:10,860 And I'm going to say, if ls bracket 0, which is 3, is less than ls 0 minus 1 153 00:07:10,860 --> 00:07:21,200 is going to be ls bracket negative 1, which is this 2 here, which 154 00:07:21,200 --> 00:07:26,720 I guess will not be a problem here. 155 00:07:26,720 --> 00:07:32,810 Because if 3-- the only case when this first element 156 00:07:32,810 --> 00:07:35,660 is going to be less than the last element 157 00:07:35,660 --> 00:07:38,330 is when the array is not rotated at all. 158 00:07:38,330 --> 00:07:42,800 So I would want to return 0 in that case. 159 00:07:42,800 --> 00:07:48,620 That actually makes me think that I may not need this "return 0" at the end 160 00:07:48,620 --> 00:07:49,910 here-- 161 00:07:49,910 --> 00:07:53,990 just kind of a peculiarity of Python indexing, 162 00:07:53,990 --> 00:07:57,500 where if I say ls bracket negative 1, it's 163 00:07:57,500 --> 00:08:01,550 going to be the last element of the list, instead of giving me an error, 164 00:08:01,550 --> 00:08:04,377 like it might in C, or Java, or some other programming language. 165 00:08:04,377 --> 00:08:06,710 SPEAKER 1: Yeah, [? think so. ?] Hadn't thought of that, 166 00:08:06,710 --> 00:08:08,450 but I think you're right. 167 00:08:08,450 --> 00:08:10,400 SPEAKER 2: All right. 168 00:08:10,400 --> 00:08:13,620 And then finishing going through that example, for this one, 169 00:08:13,620 --> 00:08:20,150 it would start out at 0 and see that 3 is, in fact, greater than 2. 170 00:08:20,150 --> 00:08:21,903 So it'll continue. 171 00:08:21,903 --> 00:08:22,820 It'll get to this one. 172 00:08:22,820 --> 00:08:25,860 It'll say that 4 is greater than 3, so it will continue. 173 00:08:25,860 --> 00:08:28,970 It'll get to 5, say 5 is greater than 4, so it'll continue. 174 00:08:28,970 --> 00:08:35,570 But then, when i is 3, we'll see that ls bracket i is, in fact, 175 00:08:35,570 --> 00:08:37,669 less than ls bracket i minus 1. 176 00:08:37,669 --> 00:08:43,789 So we'll go ahead and return i, which is 3, which is as expected. 177 00:08:43,789 --> 00:08:47,960 Just running through it as a human, that seems to work. 178 00:08:47,960 --> 00:08:51,530 Now, let's move on to writing some tests. 179 00:08:51,530 --> 00:08:54,350 I can go ahead and say-- 180 00:08:54,350 --> 00:08:58,150 I'll just print one out first to verify. 181 00:08:58,150 --> 00:09:02,200 I'll go ahead and say, print get_rotate_numbers 182 00:09:02,200 --> 00:09:06,070 of our first list here. 183 00:09:06,070 --> 00:09:12,610 And hopefully, this will end up with 3, so I can go ahead and run my code here. 184 00:09:12,610 --> 00:09:16,920 And we've got a problem here where I'm saying, 185 00:09:16,920 --> 00:09:20,290 "list object cannot be interpreted as an integer." 186 00:09:20,290 --> 00:09:20,830 Oh, OK. 187 00:09:20,830 --> 00:09:25,840 And I think what's going on here is, I can't just say for i in range lists, 188 00:09:25,840 --> 00:09:27,740 because range has to take in an integer. 189 00:09:27,740 --> 00:09:30,960 So I actually have to look at the length of the list-- 190 00:09:30,960 --> 00:09:32,560 SPEAKER 1: Yeah, that's right. 191 00:09:32,560 --> 00:09:33,550 SPEAKER 2: --instead. 192 00:09:33,550 --> 00:09:35,510 Now, I'll go ahead and try that again. 193 00:09:35,510 --> 00:09:36,010 All right. 194 00:09:36,010 --> 00:09:36,940 Nice. 195 00:09:36,940 --> 00:09:38,290 That's looking pretty good. 196 00:09:38,290 --> 00:09:40,270 That's looking like it's printing 3. 197 00:09:40,270 --> 00:09:45,970 And then I'll just go ahead and try with our other lists here. 198 00:09:45,970 --> 00:09:50,850 Hopefully, this second one should translate to 4, 199 00:09:50,850 --> 00:09:58,420 this third one should translate to 3, and this last one 200 00:09:58,420 --> 00:10:01,360 should translate to 0. 201 00:10:01,360 --> 00:10:04,110 And we'll go ahead and run that. 202 00:10:04,110 --> 00:10:07,950 And it looks like I added-- 203 00:10:07,950 --> 00:10:08,533 oh, I forgot a 204 00:10:08,533 --> 00:10:10,742 SPEAKER 1: Yeah, just [INAUDIBLE] open bracket there. 205 00:10:10,742 --> 00:10:11,880 SPEAKER 2: --bracket here. 206 00:10:11,880 --> 00:10:13,730 I'll run that. 207 00:10:13,730 --> 00:10:14,690 And it looks like-- 208 00:10:14,690 --> 00:10:15,320 SPEAKER 1: [INAUDIBLE] Looks right. 209 00:10:15,320 --> 00:10:17,750 SPEAKER 2: --that has given us the result we want. 210 00:10:17,750 --> 00:10:19,310 That's looking pretty good to me. 211 00:10:19,310 --> 00:10:21,230 I guess I'll check in at this point and see 212 00:10:21,230 --> 00:10:23,810 if there's anything that you notice about this, 213 00:10:23,810 --> 00:10:26,330 or any other corner cases you think I should try out. 214 00:10:26,330 --> 00:10:28,790 SPEAKER 1: Yeah, this looks right to me. 215 00:10:28,790 --> 00:10:31,265 What is the runtime of this? 216 00:10:31,265 --> 00:10:32,390 SPEAKER 2: Yeah, of course. 217 00:10:32,390 --> 00:10:38,120 Going through the runtime, since I'm going through i in range length of ls, 218 00:10:38,120 --> 00:10:42,350 I'm going to go through this loop a maximum of n times if there's 219 00:10:42,350 --> 00:10:44,270 n elements in ls. 220 00:10:44,270 --> 00:10:48,620 And then just accessing elements of a list in Python is O of 1, 221 00:10:48,620 --> 00:10:52,850 and comparing to integers in Python is going to be O of 1 222 00:10:52,850 --> 00:10:54,305 in terms of the size of the list. 223 00:10:54,305 --> 00:10:56,870 224 00:10:56,870 --> 00:11:00,810 This whole operation inside the "for" loop is going to be constant time. 225 00:11:00,810 --> 00:11:05,810 So I'm going to say that the entire runtime is going to be O of n. 226 00:11:05,810 --> 00:11:09,650 If there are n elements in the list, it will take a maximum of n times. 227 00:11:09,650 --> 00:11:11,600 SPEAKER 1: Yeah, I think that's right. 228 00:11:11,600 --> 00:11:14,540 Can you think of any ways to make it faster? 229 00:11:14,540 --> 00:11:17,420 SPEAKER 2: Yeah, let's see. 230 00:11:17,420 --> 00:11:23,270 If I'm working on making it faster, I wonder-- 231 00:11:23,270 --> 00:11:29,770 232 00:11:29,770 --> 00:11:39,930 I guess any way that we could make it faster would be to-- 233 00:11:39,930 --> 00:11:41,740 hmm. 234 00:11:41,740 --> 00:11:47,760 I'm actually a little bit unsure, because going through it as a human, 235 00:11:47,760 --> 00:11:51,300 I can't think of anything else I would do than go through each element. 236 00:11:51,300 --> 00:11:55,240 So I I'd love know if you have any hints, if you could nudge me 237 00:11:55,240 --> 00:11:56,740 in the right direction a little bit. 238 00:11:56,740 --> 00:11:58,320 SPEAKER 1: Yeah. 239 00:11:58,320 --> 00:12:00,870 Keep in mind that the list is sorted. 240 00:12:00,870 --> 00:12:04,530 Even though it's rotated, we have this property that it's sorted. 241 00:12:04,530 --> 00:12:08,490 Is there any search we could use that leverages the fact that it's sorted? 242 00:12:08,490 --> 00:12:11,840 243 00:12:11,840 --> 00:12:13,970 SPEAKER 2: We could use-- 244 00:12:13,970 --> 00:12:18,605 generally, with the sorted list, we could use just a binary search. 245 00:12:18,605 --> 00:12:24,620 246 00:12:24,620 --> 00:12:28,790 If we're going through and doing that, then how 247 00:12:28,790 --> 00:12:35,270 would I apply a binary search to this problem? 248 00:12:35,270 --> 00:12:38,810 I guess I could-- 249 00:12:38,810 --> 00:12:39,680 let's see. 250 00:12:39,680 --> 00:12:42,590 If I go through kind of the motions of doing 251 00:12:42,590 --> 00:12:47,550 a binary search with a problem like this, I would start in the middle 252 00:12:47,550 --> 00:12:52,205 and see that I've got of size 5 here. 253 00:12:52,205 --> 00:12:55,250 254 00:12:55,250 --> 00:12:57,770 I guess I would have to look at the first element first, 255 00:12:57,770 --> 00:12:59,660 see that my first element is a 3. 256 00:12:59,660 --> 00:13:02,900 And then when I head to the middle, I see that I'm 257 00:13:02,900 --> 00:13:06,980 at size 5, which means that when-- 258 00:13:06,980 --> 00:13:09,590 it's been increasing since then. 259 00:13:09,590 --> 00:13:13,820 Which means-- I guess, at that point, I can go ahead and narrow my search down 260 00:13:13,820 --> 00:13:19,000 to the latter half of the list after I've checked that one. 261 00:13:19,000 --> 00:13:20,140 And vice versa. 262 00:13:20,140 --> 00:13:23,350 If I, let's say for-- what's a good example? 263 00:13:23,350 --> 00:13:28,570 For this one, if I start at-- 264 00:13:28,570 --> 00:13:31,720 or I guess a better-- 265 00:13:31,720 --> 00:13:34,120 I guess I don't have a great example for that one. 266 00:13:34,120 --> 00:13:39,190 But if I were to get to a point where I was checking this 3 here, 267 00:13:39,190 --> 00:13:41,890 then I would know if I'm checking at this 3, 268 00:13:41,890 --> 00:13:46,660 I know I can just look at everything before the 3. 269 00:13:46,660 --> 00:13:51,990 Yeah, I think a binary search would be able to help us out there. 270 00:13:51,990 --> 00:13:54,130 Just want to check in time-wise. 271 00:13:54,130 --> 00:13:56,830 Is it all right if I go ahead and try and implement that, 272 00:13:56,830 --> 00:13:58,905 or do you think we should move on? 273 00:13:58,905 --> 00:14:01,030 SPEAKER 1: Yeah, let's try to implement it quickly, 274 00:14:01,030 --> 00:14:03,550 and then if we run out of time, that's totally fine. 275 00:14:03,550 --> 00:14:04,630 SPEAKER 2: Yeah, sure. 276 00:14:04,630 --> 00:14:12,420 Let me leave this other one here, just to have something to reference. 277 00:14:12,420 --> 00:14:15,660 And now, this newer version here. 278 00:14:15,660 --> 00:14:22,770 I don't necessarily want to go through each i in this range. 279 00:14:22,770 --> 00:14:26,850 I want to go ahead and say my-- 280 00:14:26,850 --> 00:14:29,010 let's see. 281 00:14:29,010 --> 00:14:35,830 I only care about when I'm going from a high number to a lower number. 282 00:14:35,830 --> 00:14:40,590 So I'll go ahead and say that my highest number that I've seen so far 283 00:14:40,590 --> 00:14:46,920 is going to be the first element in the list, is ls bracket 0. 284 00:14:46,920 --> 00:14:55,140 And then I can go ahead and say that my lowest element that I've seen so far 285 00:14:55,140 --> 00:14:57,780 is-- 286 00:14:57,780 --> 00:15:02,220 we can go ahead and look at the last element of the list, 287 00:15:02,220 --> 00:15:06,840 because I know it's going to be somewhere in between-- 288 00:15:06,840 --> 00:15:10,050 or I guess we don't necessarily know that's the lowest. 289 00:15:10,050 --> 00:15:14,070 Let me think about how we would want to initialize those. 290 00:15:14,070 --> 00:15:16,710 291 00:15:16,710 --> 00:15:17,850 5. 292 00:15:17,850 --> 00:15:20,370 If that is the lowest, then-- 293 00:15:20,370 --> 00:15:22,748 yeah, I guess I'll just start out with 0 and go 294 00:15:22,748 --> 00:15:24,165 through kind of the logic of this. 295 00:15:24,165 --> 00:15:28,860 296 00:15:28,860 --> 00:15:36,570 Although, I think I'm going to actually want-- 297 00:15:36,570 --> 00:15:42,130 if I'm looking for an item that is lower here, 298 00:15:42,130 --> 00:15:47,230 I'm also going to want to keep track of the indices that I'm working with. 299 00:15:47,230 --> 00:15:49,690 Does that seem like it's going to be on the right track? 300 00:15:49,690 --> 00:15:50,357 SPEAKER 1: Yeah. 301 00:15:50,357 --> 00:15:53,090 I think, in general, you'll probably want to look at the left-- 302 00:15:53,090 --> 00:15:55,643 keep track of the left and right endpoints of the search 303 00:15:55,643 --> 00:15:58,060 so then you can compare wherever you land on in the middle 304 00:15:58,060 --> 00:16:00,190 to those left and right endpoints. 305 00:16:00,190 --> 00:16:03,490 SPEAKER 2: Yeah, that's a good point. 306 00:16:03,490 --> 00:16:09,730 Let me go ahead and say that left, for now, is going to be 0, the first index. 307 00:16:09,730 --> 00:16:12,400 And then since we're starting our search with the full list, 308 00:16:12,400 --> 00:16:17,515 our right is going to be the length of the list minus 1. 309 00:16:17,515 --> 00:16:20,180 310 00:16:20,180 --> 00:16:24,740 And then what I can go ahead and say-- 311 00:16:24,740 --> 00:16:28,550 I can go ahead and, instead of having this whole "for" loop here, 312 00:16:28,550 --> 00:16:33,290 I can say while right is greater than left-- 313 00:16:33,290 --> 00:16:37,760 so while we're still working on converging in-- 314 00:16:37,760 --> 00:16:42,080 then I'll go ahead and say that my current index is 315 00:16:42,080 --> 00:16:49,500 going to be equal to right plus left divided by 2. 316 00:16:49,500 --> 00:16:54,060 Let me get some parentheses in there. 317 00:16:54,060 --> 00:16:56,702 That will take the middle element. 318 00:16:56,702 --> 00:16:58,410 And then since we're working in Python, I 319 00:16:58,410 --> 00:17:02,790 realize I should probably do some integer division here. 320 00:17:02,790 --> 00:17:06,250 That will get us our current index that we're working with. 321 00:17:06,250 --> 00:17:10,109 And then I can go ahead and say-- 322 00:17:10,109 --> 00:17:12,660 and let me look at this example to see what we should do. 323 00:17:12,660 --> 00:17:20,069 In this example, if our current index is greater than the index on the left, 324 00:17:20,069 --> 00:17:23,670 then I know I can narrow my search to the right half. 325 00:17:23,670 --> 00:17:27,650 If ls bracket current-- 326 00:17:27,650 --> 00:17:33,110 if that current number is greater than ls bracket left, 327 00:17:33,110 --> 00:17:36,980 is greater than the left number, then I can go ahead 328 00:17:36,980 --> 00:17:41,600 and I can narrow down the search to this right half of the list. 329 00:17:41,600 --> 00:17:48,810 I can go ahead and say that left equals current. 330 00:17:48,810 --> 00:17:53,580 And then I can go ahead and say, otherwise, 331 00:17:53,580 --> 00:18:06,290 if ls bracket current is less than ls bracket left, 332 00:18:06,290 --> 00:18:13,470 then I can go ahead and say right equals current. 333 00:18:13,470 --> 00:18:21,810 I know that we are going ahead and changing our rightmost there. 334 00:18:21,810 --> 00:18:27,210 And let me-- now, we just kind of have to work 335 00:18:27,210 --> 00:18:31,770 on what happens after we do narrow in on that case. 336 00:18:31,770 --> 00:18:35,040 Let's go through the example with this top one again. 337 00:18:35,040 --> 00:18:38,260 We get to this point with this 5 here. 338 00:18:38,260 --> 00:18:42,210 And so now we know that our difference is going to be between 5 and 2. 339 00:18:42,210 --> 00:18:45,720 And actually, now that I'm thinking of-- 340 00:18:45,720 --> 00:18:46,770 yes. 341 00:18:46,770 --> 00:18:49,630 We're looking between 5 and 2 here. 342 00:18:49,630 --> 00:18:56,700 So our left, at this point, is going to be 2, and our right is going to be 4. 343 00:18:56,700 --> 00:19:00,960 Now, our central one is going to be 1 here. 344 00:19:00,960 --> 00:19:06,250 Now, since 1 is less than 5, we would hit this case. 345 00:19:06,250 --> 00:19:08,340 And so we would say right equals current. 346 00:19:08,340 --> 00:19:13,050 Now, our left is going to be 5 and our right is going to be 1. 347 00:19:13,050 --> 00:19:20,370 We know that we're ending here when our right one is just 1 348 00:19:20,370 --> 00:19:24,150 more than our left one. 349 00:19:24,150 --> 00:19:27,960 Let me go through what the example would do in this if left is 2, 350 00:19:27,960 --> 00:19:31,560 as we have here, and right is 3. 351 00:19:31,560 --> 00:19:36,750 When left is 2 and right is 3, our current is going to be 3. 352 00:19:36,750 --> 00:19:40,680 This is going to say, if current is greater than the left one-- which isn't 353 00:19:40,680 --> 00:19:42,870 true, because they're the same thing. 354 00:19:42,870 --> 00:19:48,900 And then we'll say, if current is less than the left one, which 355 00:19:48,900 --> 00:19:52,150 isn't going to be true because they're the same, 356 00:19:52,150 --> 00:19:54,760 then we can have an "else" statement here. 357 00:19:54,760 --> 00:19:58,080 And if it's an "else," then we know that this current one 358 00:19:58,080 --> 00:20:01,690 is kind of 1 below where we want to do. 359 00:20:01,690 --> 00:20:10,840 We can try and return our right here. 360 00:20:10,840 --> 00:20:15,700 Now, just running through another example as kind of a sanity check, 361 00:20:15,700 --> 00:20:18,920 we'll take this one here. 362 00:20:18,920 --> 00:20:24,050 Let's say-- our left is 0 to start. 363 00:20:24,050 --> 00:20:25,310 Right is 4. 364 00:20:25,310 --> 00:20:31,060 We can find the one in the middle, which is going to be element 2. 365 00:20:31,060 --> 00:20:35,530 And then we're going to see that 2 is greater than our left. 366 00:20:35,530 --> 00:20:41,200 That means that we're going to narrow our search down to these last three 367 00:20:41,200 --> 00:20:43,860 elements here. 368 00:20:43,860 --> 00:20:48,750 And now, we're going to go ahead and say that-- 369 00:20:48,750 --> 00:20:49,500 yeah. 370 00:20:49,500 --> 00:20:53,400 Now, we're going to go ahead and find the middle element here, which is 1. 371 00:20:53,400 --> 00:20:59,020 And we'll say that left-- 372 00:20:59,020 --> 00:20:59,520 yeah. 373 00:20:59,520 --> 00:21:00,353 This is our current. 374 00:21:00,353 --> 00:21:03,720 And then we're checking, is current greater than left? 375 00:21:03,720 --> 00:21:04,830 No, that's not true. 376 00:21:04,830 --> 00:21:06,210 Is current less than left? 377 00:21:06,210 --> 00:21:07,390 Yes, that is true. 378 00:21:07,390 --> 00:21:10,590 So we're changing our current to this-- 379 00:21:10,590 --> 00:21:13,290 or, we're changing our right to this. 380 00:21:13,290 --> 00:21:15,840 Now, we're just looking at this section here. 381 00:21:15,840 --> 00:21:17,490 These are our left and right. 382 00:21:17,490 --> 00:21:22,543 And when we compare left to current and right to current, 383 00:21:22,543 --> 00:21:24,210 they're both going to be the same thing. 384 00:21:24,210 --> 00:21:26,550 We get this "else" here, and we return what's 385 00:21:26,550 --> 00:21:32,100 on the right, which is 1, which should be correct. 386 00:21:32,100 --> 00:21:40,410 Just basic conceptually-wise, it looks like things are working out here. 387 00:21:40,410 --> 00:21:44,790 Let me run through it real quick with the un-rotated array 388 00:21:44,790 --> 00:21:46,920 to see how things are going there. 389 00:21:46,920 --> 00:21:49,740 In this case, we're going to get to this middle one. 390 00:21:49,740 --> 00:21:52,230 We're going to see that right is greater than-- 391 00:21:52,230 --> 00:21:54,600 or yeah, the current is greater than the left. 392 00:21:54,600 --> 00:21:57,060 We'll get to this one here now, and we'll 393 00:21:57,060 --> 00:22:01,215 see that the right is still greater than the left. 394 00:22:01,215 --> 00:22:05,460 395 00:22:05,460 --> 00:22:11,850 Our current is still greater than the left, so our left is becoming this one. 396 00:22:11,850 --> 00:22:19,050 And now, we're going to go ahead and say the left is still going to be this one. 397 00:22:19,050 --> 00:22:22,020 So that's not going to give us the right answer here, it looks like. 398 00:22:22,020 --> 00:22:25,020 SPEAKER 1: Yeah, I think the stop condition you're looking for, 399 00:22:25,020 --> 00:22:29,070 sort of in that first example, you can see, with the 1, the number to the left 400 00:22:29,070 --> 00:22:31,410 is bigger and the number to the right is bigger. 401 00:22:31,410 --> 00:22:33,720 That's kind of the stop condition for your search. 402 00:22:33,720 --> 00:22:36,780 Otherwise, though, I think the binary search is right. 403 00:22:36,780 --> 00:22:37,710 SPEAKER 2: Oh, OK. 404 00:22:37,710 --> 00:22:39,630 Yeah, that makes sense. 405 00:22:39,630 --> 00:22:45,300 Maybe I can go ahead and check that condition. 406 00:22:45,300 --> 00:22:49,950 If we're looking at our current one, we would-- 407 00:22:49,950 --> 00:22:54,540 would we-- do you think, for each time, we would look at our current and check 408 00:22:54,540 --> 00:22:58,710 if it's smaller than the left one and greater-- 409 00:22:58,710 --> 00:23:01,833 smaller than the left one and smaller than the right one? 410 00:23:01,833 --> 00:23:03,250 SPEAKER 1: Yeah, that seems right. 411 00:23:03,250 --> 00:23:04,250 SPEAKER 2: And then it-- 412 00:23:04,250 --> 00:23:06,450 OK, sure. 413 00:23:06,450 --> 00:23:11,760 We're already checking if our current is smaller than the left one here. 414 00:23:11,760 --> 00:23:14,370 415 00:23:14,370 --> 00:23:17,790 I can go ahead and nest a little bit of "ifs" 416 00:23:17,790 --> 00:23:32,230 here and say, if our current is also smaller than the one-- 417 00:23:32,230 --> 00:23:32,980 oh, OK. 418 00:23:32,980 --> 00:23:33,790 Sorry, sorry. 419 00:23:33,790 --> 00:23:36,620 But we're not looking at direct neighbors there. 420 00:23:36,620 --> 00:23:39,490 So let's look at direct neighbors up here. 421 00:23:39,490 --> 00:23:48,290 That would look like if ls bracket current minus 1 422 00:23:48,290 --> 00:23:57,970 is less ls bracket current, which is less than ls bracket current plus 1-- 423 00:23:57,970 --> 00:24:01,060 which is a nice thing we can do in Python, 424 00:24:01,060 --> 00:24:05,950 is just combine these different inequalities. 425 00:24:05,950 --> 00:24:09,100 And I'll take away those parentheses for now. 426 00:24:09,100 --> 00:24:12,320 In this case, we know that current is the one that we want to return. 427 00:24:12,320 --> 00:24:15,190 So we can go ahead and return current here. 428 00:24:15,190 --> 00:24:17,960 429 00:24:17,960 --> 00:24:25,668 And then let me just do another sanity check. 430 00:24:25,668 --> 00:24:26,210 Would these-- 431 00:24:26,210 --> 00:24:28,280 SPEAKER 1: Yeah, I think this looks this looks basically right. 432 00:24:28,280 --> 00:24:30,320 Just for time, we're basically at time. 433 00:24:30,320 --> 00:24:34,395 But yeah, overall, this search looks pretty good. 434 00:24:34,395 --> 00:24:35,270 SPEAKER 2: All right. 435 00:24:35,270 --> 00:24:35,710 SPEAKER 1: Awesome. 436 00:24:35,710 --> 00:24:38,210 Well, thanks for taking the time for chatting with me today, 437 00:24:38,210 --> 00:24:39,800 and have a great rest of your day. 438 00:24:39,800 --> 00:24:40,340 SPEAKER 2: Yeah, thanks. 439 00:24:40,340 --> 00:24:41,420 It was great to meet you. 440 00:24:41,420 --> 00:24:42,212 SPEAKER 1: Awesome. 441 00:24:42,212 --> 00:24:43,570 See you later. 442 00:24:43,570 --> 00:24:44,429