1 00:00:00,520 --> 00:00:00,970 OK. 2 00:00:01,000 --> 00:00:06,480 Welcome back to another lecture, we're going to continue on with the topic of searching and searching 3 00:00:06,490 --> 00:00:11,410 algorithms in today's lecture is going to talk specifically about a new search algorithm called the 4 00:00:11,410 --> 00:00:12,280 binary search. 5 00:00:13,450 --> 00:00:17,890 So let's think about what we've done so far in searching, which is only leading our search. 6 00:00:18,070 --> 00:00:20,040 Is there a faster search? 7 00:00:20,050 --> 00:00:21,840 Do you think there's a faster search? 8 00:00:22,180 --> 00:00:23,590 Are linear or sequential? 9 00:00:23,590 --> 00:00:28,150 Search had to go through every single element, which makes sense, right? 10 00:00:28,150 --> 00:00:32,530 Because if the elements are out of order, then the thing we're looking for, it could be anywhere inside 11 00:00:32,530 --> 00:00:33,640 of that vector array. 12 00:00:33,650 --> 00:00:36,360 So we need to check every single position, right? 13 00:00:36,400 --> 00:00:38,500 Because it could be any one of those positions. 14 00:00:39,280 --> 00:00:45,910 But what if, hypothetically, all of the elements were sorted and sorted in ascending order? 15 00:00:46,890 --> 00:00:52,400 So think about that and think a little more specifically, if I'm looking, let's say, for the number 16 00:00:52,410 --> 00:00:55,080 five in an array of vector that is sorted. 17 00:00:55,620 --> 00:01:01,260 Let's say I checked some position near the middle of that array or vector, and I noticed that there 18 00:01:01,260 --> 00:01:03,570 is an element six there. 19 00:01:03,570 --> 00:01:10,560 So the item is an integer, which is the integer six at that position. 20 00:01:10,560 --> 00:01:16,050 So some middle of the array, whatever to that position, might be somewhere near the middle. 21 00:01:16,200 --> 00:01:18,480 I find an item that is six. 22 00:01:19,520 --> 00:01:26,060 If I find this item at six and I'm looking for five, does it make sense to look further to the right? 23 00:01:27,150 --> 00:01:28,590 Of where that six is. 24 00:01:29,370 --> 00:01:35,070 So think about this, does it make sense for us to look further to the right if the array is sorted 25 00:01:35,070 --> 00:01:36,630 and we're looking for the number five? 26 00:01:38,880 --> 00:01:44,550 So the answer is, no, we do not need to look further to the right because everything to the right 27 00:01:44,550 --> 00:01:49,940 of six is not only bigger than five, it's bigger than six and six is bigger than five. 28 00:01:49,950 --> 00:01:52,500 So none of those numbers are of interest to us. 29 00:01:53,310 --> 00:02:00,180 In fact, we can pretty much pretend that the list is only everything to the left of the position that's 30 00:02:00,180 --> 00:02:01,420 holding the number six. 31 00:02:02,010 --> 00:02:04,780 And this is the main mechanism of binary search. 32 00:02:04,800 --> 00:02:09,990 It basically cuts out the parts of the array of vector that we don't need, and it makes the area that 33 00:02:09,990 --> 00:02:13,200 we have to search much smaller each time we do this. 34 00:02:13,860 --> 00:02:17,490 In turn, this speeds up the overall searching process by a lot. 35 00:02:19,570 --> 00:02:24,910 So let's see how it works, exactly, we're going to look in a more detailed example here, I have eight 36 00:02:24,910 --> 00:02:27,160 items in an array or vector. 37 00:02:28,180 --> 00:02:34,220 What I'm going to do is I'm going to start at vector dot size minus one divided by two. 38 00:02:34,240 --> 00:02:36,160 So what is vector dot size minus one? 39 00:02:36,180 --> 00:02:38,740 It's seven when I divide seven by two. 40 00:02:39,830 --> 00:02:42,890 It is three, so we're doing integer division right here. 41 00:02:43,580 --> 00:02:49,190 So what we're really doing, which you'll see in the rest of the algorithm is we are adding the first 42 00:02:49,190 --> 00:02:55,700 position, which is zero plus the last position, which is seven, which gives us seven zero plus seven 43 00:02:55,700 --> 00:02:57,080 kind of in parentheses here. 44 00:02:58,190 --> 00:02:59,100 Divided by two. 45 00:02:59,120 --> 00:03:01,910 Except I didn't put the zero there because it's zero. 46 00:03:02,600 --> 00:03:06,900 So we're starting out right here at three, so it's kind of near the middle. 47 00:03:06,920 --> 00:03:11,090 The actual middle since there's eight items, is this line right here, but we can't just be on the 48 00:03:11,090 --> 00:03:11,420 line. 49 00:03:11,420 --> 00:03:12,770 We got to be in an actual position. 50 00:03:12,770 --> 00:03:16,460 So we kind of like our rounding down to this three right here. 51 00:03:18,790 --> 00:03:24,580 So let's see, the number we're looking for is 22 is 22 greater than nine or 22 less than nine. 52 00:03:24,620 --> 00:03:29,530 Well, it's greater than nine, so we want to look only to the right of nine. 53 00:03:29,530 --> 00:03:33,010 We do not want to look to the left of nine. 54 00:03:33,500 --> 00:03:33,760 Right. 55 00:03:34,540 --> 00:03:38,680 So what we're going to do is pretend this part of the array is now invisible. 56 00:03:38,690 --> 00:03:40,720 We're not going to change the position numbers. 57 00:03:40,720 --> 00:03:43,600 We're just going to pretend that is completely invisible. 58 00:03:43,600 --> 00:03:44,590 We have no interest in it. 59 00:03:44,590 --> 00:03:50,830 We only have an interest in what was to the right of nine right and the right of nine starts right here. 60 00:03:52,670 --> 00:03:57,140 So we now need to find a new middle for this sub array. 61 00:03:57,200 --> 00:03:57,520 Right? 62 00:03:58,670 --> 00:04:00,500 So what we're going to do is the same thing. 63 00:04:00,500 --> 00:04:06,350 We're going to add the first position index, right, the first index, plus the last index. 64 00:04:07,540 --> 00:04:14,980 Add those together, so seven plus four is 11, and then we divide 11 by two and we're going to get 65 00:04:14,980 --> 00:04:20,440 five because we're doing integer division, so that will give us our new middle to consider. 66 00:04:22,340 --> 00:04:28,720 And each time that we're doing this, when you see a green square, we're also checking, you know, 67 00:04:28,730 --> 00:04:33,320 we're of course seen as a greater or is it less than, you know, the number we're looking for, but 68 00:04:33,320 --> 00:04:35,540 we're also curious about whether it's equal as well. 69 00:04:35,550 --> 00:04:41,660 So if any point in time, the green square here was equal to twenty two, we would know that we found 70 00:04:41,660 --> 00:04:42,380 our answer. 71 00:04:45,140 --> 00:04:53,690 So we take a look at this 16, so is 20 to greater than 16 or 20 to less than 16, well, it's greater 72 00:04:53,690 --> 00:04:54,370 than 16. 73 00:04:54,380 --> 00:04:59,560 So once again, we're going to ignore everything that's not to the right of 16, so we're going to ignore 74 00:04:59,720 --> 00:05:01,370 16 and 14. 75 00:05:02,330 --> 00:05:04,520 So we pretty much make those invisible. 76 00:05:04,520 --> 00:05:06,050 And now we're left with these two items. 77 00:05:06,050 --> 00:05:07,850 Here we have six and seven. 78 00:05:08,450 --> 00:05:10,610 Once again, we need to calculate a new middle. 79 00:05:10,790 --> 00:05:13,100 We do six plus seven, right? 80 00:05:13,100 --> 00:05:15,980 So the lowest plus the highest index. 81 00:05:16,580 --> 00:05:24,680 So we have six plus seven is 13 and we divide 13 by two and that gives us six. 82 00:05:25,160 --> 00:05:29,450 So now we are in position six and we'll look at that. 83 00:05:29,450 --> 00:05:35,210 The number we're looking for is twenty two and just so happens that we found twenty to twenty two is 84 00:05:35,210 --> 00:05:37,880 not greater than doing two or less than twenty two. 85 00:05:37,880 --> 00:05:39,620 It is equal to our answer. 86 00:05:39,620 --> 00:05:40,850 And so we have found it. 87 00:05:42,530 --> 00:05:44,280 So we found her answer pretty fast. 88 00:05:44,300 --> 00:05:48,860 I mean, compare that to us having to look at all the elements like in linear search. 89 00:05:49,490 --> 00:05:53,750 So if we were doing linear search, we would have to just start over here and look at this element, 90 00:05:54,080 --> 00:05:58,460 then look at this element, then look at this element, then look at this element and that one and that 91 00:05:58,460 --> 00:05:58,730 one. 92 00:05:59,090 --> 00:06:02,180 And then we would finally arrive here at our answer. 93 00:06:02,180 --> 00:06:03,830 But that's a lot of comparisons. 94 00:06:03,830 --> 00:06:10,340 If we go back, we noticed that we only did a few comparisons, so we started with nine nine wasn't 95 00:06:10,340 --> 00:06:10,910 the answer. 96 00:06:12,320 --> 00:06:16,760 Then we looked here at 16 and 16 wasn't the answer, and then we found her answer. 97 00:06:16,770 --> 00:06:17,420 22. 98 00:06:18,590 --> 00:06:23,360 You know, that's a lot less than going through all of these positions until we, you know, we looked 99 00:06:23,360 --> 00:06:25,590 at each one of these things up until here. 100 00:06:25,610 --> 00:06:28,280 So this is a much more efficient algorithm. 101 00:06:28,280 --> 00:06:34,730 So I'm not going to go over the details of how fast each one of these algorithms is and why it's that 102 00:06:34,730 --> 00:06:39,380 fast because we're going to do that later on in the algorithm section of the course. 103 00:06:39,380 --> 00:06:41,480 We're going to look into this in great detail. 104 00:06:42,230 --> 00:06:48,170 If you want a solid answer, though, just to be able to say, you know, linear search, is this this 105 00:06:48,170 --> 00:06:50,190 fast and binary search? 106 00:06:50,190 --> 00:06:50,900 Is this fast? 107 00:06:51,230 --> 00:06:57,980 You can say that linear search runs in linear time and binary search runs in logarithmic time, except 108 00:06:57,980 --> 00:06:59,840 I haven't really explain these concepts. 109 00:07:00,140 --> 00:07:06,470 These are things that you would have to look into, but I don't think that's necessarily the best idea, 110 00:07:06,470 --> 00:07:11,720 because later in the course, we're going to dive deep into analyzing these algorithms and understanding 111 00:07:11,720 --> 00:07:16,820 what it means for something to run in linear time or logarithmic time. 112 00:07:17,900 --> 00:07:25,310 The only thing that you can like think right now is that or know is in linear time is actually slower 113 00:07:25,310 --> 00:07:26,600 than logarithmic time. 114 00:07:27,020 --> 00:07:30,240 So therefore binary search is faster than linear search. 115 00:07:30,260 --> 00:07:32,060 But we're going to get into that later. 116 00:07:33,320 --> 00:07:38,580 So let's look at another example where we do not find the item that we're looking for. 117 00:07:38,600 --> 00:07:40,100 So let's look for four. 118 00:07:41,990 --> 00:07:48,920 So what we're going to do is the same thing we're going to do is zero plus seven is seven seven, divided 119 00:07:48,920 --> 00:07:49,810 by two is three. 120 00:07:49,820 --> 00:07:52,490 So we'll start off at the same position, right for the middle. 121 00:07:53,540 --> 00:07:59,270 We're going to get rid of everything over here to the right because we're looking for four. 122 00:07:59,360 --> 00:08:01,160 Four is less than nine. 123 00:08:01,700 --> 00:08:04,430 So we don't care about nine or anything over here. 124 00:08:06,460 --> 00:08:11,640 So what we're actually doing now is we're moving our high. 125 00:08:12,070 --> 00:08:19,030 So remember, we were doing like a low, which is zero plus high, which is seven to zero plus seven. 126 00:08:20,300 --> 00:08:24,830 And we got took that answer, which is seven divided by two equals three to get the middle. 127 00:08:24,860 --> 00:08:26,290 We're going to do the same thing here. 128 00:08:26,300 --> 00:08:27,860 So now only get rid of that. 129 00:08:27,890 --> 00:08:33,440 We're basically going to say that our new high is two because it's one less than where we were right 130 00:08:33,440 --> 00:08:33,980 here, right? 131 00:08:33,990 --> 00:08:40,760 So three minus one is to our highest two and our low is zero zero plus two. 132 00:08:42,480 --> 00:08:47,440 Is to do to limit you is one, so now we have a new middle here on one. 133 00:08:48,510 --> 00:08:51,480 So is for less than three. 134 00:08:51,510 --> 00:08:53,100 No, it's not for greater than three. 135 00:08:53,130 --> 00:08:53,700 Yes, it is. 136 00:08:53,710 --> 00:08:54,660 So we're not interested. 137 00:08:54,720 --> 00:08:56,330 We're not interested in any of this right here. 138 00:08:56,340 --> 00:08:57,450 We're only interested in here. 139 00:08:57,930 --> 00:09:01,950 So now we have one element left so pretty interesting. 140 00:09:02,340 --> 00:09:04,440 So we're not going to find our answer here. 141 00:09:04,440 --> 00:09:08,700 But what we're going to do to get the middle is what we've been doing so far. 142 00:09:08,700 --> 00:09:11,370 So we're going to move the low and high index. 143 00:09:11,940 --> 00:09:16,980 So we're going to move the we're going to check for four fours less than six. 144 00:09:16,980 --> 00:09:26,280 So what we will do is we're actually going to say that the high is going to be one less than what it 145 00:09:26,280 --> 00:09:28,560 currently is right here. 146 00:09:28,950 --> 00:09:32,730 The high and low are the same ones, right? 147 00:09:32,730 --> 00:09:35,660 Currently, low equals two and high equals two. 148 00:09:35,670 --> 00:09:38,970 Since we're only on one element, there's only one element left. 149 00:09:39,420 --> 00:09:42,510 If we do, high equals mid minus one. 150 00:09:43,640 --> 00:09:50,510 So two minus one is one suddenly high is less than low, right, our high index is less than our low 151 00:09:50,510 --> 00:09:50,930 index. 152 00:09:50,930 --> 00:09:55,100 So low is two and high is one that doesn't really make sense, right? 153 00:09:55,100 --> 00:09:57,050 The high shouldn't be less than the low. 154 00:09:57,590 --> 00:09:59,660 So this tells us to stop looking. 155 00:09:59,690 --> 00:10:04,340 Unfortunately, we haven't found our item and now we can give up with our search. 156 00:10:06,580 --> 00:10:09,010 So let's go ahead and go write some code. 157 00:10:09,880 --> 00:10:13,690 So head to your favorite editor and we're going to go ahead and write this binary search. 158 00:10:16,480 --> 00:10:18,000 And to clear that up. 159 00:10:18,630 --> 00:10:24,030 And what I'm going to do is go into the first program and the searching folder here. 160 00:10:24,810 --> 00:10:31,860 So I am going to actually open up this binary search to CP, where I have an empty function skeleton 161 00:10:31,860 --> 00:10:34,170 and an empty main function skeleton. 162 00:10:34,740 --> 00:10:38,400 I'm going to make a binary search function that's a yes or no answer. 163 00:10:38,400 --> 00:10:44,310 So it's a boolean that it returns and it takes in the vector, which has the items and also takes in 164 00:10:44,310 --> 00:10:45,640 the number that we're searching for. 165 00:10:45,660 --> 00:10:47,250 So these are both the parameters. 166 00:10:48,600 --> 00:10:53,280 And what is going to do is to run the binary search in this function and return whether the item was 167 00:10:53,280 --> 00:10:53,850 found or not. 168 00:10:53,880 --> 00:10:55,440 So let's go ahead and make some stuff in. 169 00:10:55,770 --> 00:11:01,110 Of course, I want to make a vector of integers and I'm I call this my vector and I actually want to 170 00:11:01,110 --> 00:11:02,990 show you a new thing that you can do. 171 00:11:03,000 --> 00:11:10,260 You can actually initialize a vector like this with hardcoded values, not from user input just in your 172 00:11:10,260 --> 00:11:10,800 program. 173 00:11:11,340 --> 00:11:21,700 So you can put a bracket like this and you can just be like one three eight two four four five six seven 174 00:11:21,700 --> 00:11:22,470 and let's just do that. 175 00:11:23,490 --> 00:11:27,090 So I just made a vector here that contains these items. 176 00:11:28,100 --> 00:11:34,490 By just using the curly braces and, you know, an open, enclosed, open and closed curly brace and 177 00:11:34,490 --> 00:11:41,120 then comma separated values in between, so you're able to make an initialize a vector like this as 178 00:11:41,120 --> 00:11:41,450 well. 179 00:11:42,350 --> 00:11:50,480 Except one thing is that you do need to be using a version of C++ like the compiler that I believe is 180 00:11:50,480 --> 00:11:54,200 above C++ 98, I think. 181 00:11:54,500 --> 00:12:00,740 But I think that you probably should be using C++ 11 and above, no matter what you're doing, just 182 00:12:00,740 --> 00:12:02,570 because that has all the nice features. 183 00:12:02,570 --> 00:12:07,670 So just want to point that out, though, if you're using an older version of C++ when you compile this 184 00:12:07,670 --> 00:12:12,610 program, it might say, Hey, you can't do this right here with this style. 185 00:12:13,280 --> 00:12:14,420 So just be aware of that. 186 00:12:14,750 --> 00:12:20,390 So another thing that we're going to do is make an integer called number because we want the user to 187 00:12:20,390 --> 00:12:22,130 also be able to enter a number, right? 188 00:12:22,520 --> 00:12:24,460 Let's go ahead and get that number right away. 189 00:12:24,470 --> 00:12:26,030 So I'm just going to see out. 190 00:12:26,270 --> 00:12:36,210 I'm going to say enter a number to be searched in the vector because we just already have a vector, 191 00:12:36,210 --> 00:12:36,500 right? 192 00:12:37,790 --> 00:12:41,360 And then we'll say, see it, see in into the number. 193 00:12:42,920 --> 00:12:47,810 And so what we're going to do now is we're actually just going to send the vector into our binary search, 194 00:12:47,810 --> 00:12:50,690 the vector and the number to see if we can find it so. 195 00:12:52,070 --> 00:12:59,540 What I want to do is I'm going to put an F because my binary search function returns a Boolean so I 196 00:12:59,540 --> 00:13:06,170 can use an F right here and I'll just have the f be dependent on the return from the function so I can 197 00:13:06,170 --> 00:13:14,270 just put a function, call right and say binary search, and I'm going to just pass my act and I'm going 198 00:13:14,270 --> 00:13:16,490 to pass the number. 199 00:13:17,450 --> 00:13:27,140 And so if this function call returns true, then the F will evaluate to true and the code inside the 200 00:13:27,140 --> 00:13:29,510 F will be executed so we can just print out. 201 00:13:29,510 --> 00:13:31,520 If that's the case, that means we found it right. 202 00:13:31,520 --> 00:13:42,860 So we'll say, say we let's just say we found the number number in the vector. 203 00:13:44,660 --> 00:13:45,680 So how about that? 204 00:13:47,950 --> 00:13:56,740 Inline and then we'll say else, and then we'll just say we did not find meaning. 205 00:13:57,000 --> 00:14:00,700 No, no. 206 00:14:01,420 --> 00:14:06,280 And the victor, of course. 207 00:14:08,120 --> 00:14:12,220 Cool, so we can just leave it like that. 208 00:14:12,610 --> 00:14:15,520 And so let's go ahead and figure out our binary search now. 209 00:14:15,550 --> 00:14:15,890 All right. 210 00:14:15,910 --> 00:14:19,360 Because we got everything else set up, we're just going to call binary search here is going to tell 211 00:14:19,360 --> 00:14:20,860 us whether it actually found it or not. 212 00:14:20,860 --> 00:14:22,990 And then we can print out the proper message. 213 00:14:25,060 --> 00:14:27,280 So what are we going to do for binary search? 214 00:14:27,310 --> 00:14:31,100 Well, one thing, one thing that we're going to need is some local variables, right? 215 00:14:31,120 --> 00:14:36,250 We need to represent that low index and that high index, and we're going to keep changing the low and 216 00:14:36,250 --> 00:14:37,000 high index. 217 00:14:37,570 --> 00:14:43,000 And that's going to tell us whatever's in between low and high is the region of the vector that we care 218 00:14:43,000 --> 00:14:43,270 about. 219 00:14:43,270 --> 00:14:47,980 Remember, the rest kind of turns invisible because we realize we don't need to look in those sections. 220 00:14:48,520 --> 00:14:55,690 Low and high are going to be these little sliding kind of windows that show us what parts of the vector 221 00:14:55,690 --> 00:14:56,860 we're going to want to look into. 222 00:14:56,890 --> 00:14:57,220 OK. 223 00:14:58,300 --> 00:15:08,310 So I'm going to say and low equals zero to start out with and then I'll say and high equals v right 224 00:15:08,320 --> 00:15:10,510 v is the variable we have right here. 225 00:15:10,510 --> 00:15:11,980 That's local to our function. 226 00:15:11,980 --> 00:15:14,230 And it's also passed by reference, if you notice. 227 00:15:15,740 --> 00:15:23,150 So I'm going to do in high equals v that size minus one, because that'll give us the very last next 228 00:15:23,150 --> 00:15:24,200 to start out with, right? 229 00:15:24,230 --> 00:15:29,990 Think back to the example we had zero in the beginning and then we had seven at the end because we had 230 00:15:29,990 --> 00:15:30,950 eight items, right? 231 00:15:31,190 --> 00:15:35,030 And we were using zero plus seven equals seven, divided by two. 232 00:15:35,480 --> 00:15:41,030 That gave us three, right, which was supposed to be our middle, our starting out middle right. 233 00:15:41,570 --> 00:15:43,190 That is the first middle that we have. 234 00:15:44,570 --> 00:15:46,370 So this will give us a proper, low and high. 235 00:15:46,790 --> 00:15:48,890 I'm going to start off immediately with the wow loop. 236 00:15:48,890 --> 00:15:50,340 And how long do we loop? 237 00:15:50,360 --> 00:15:53,900 What was our stopping condition if we didn't find something? 238 00:15:53,910 --> 00:15:54,950 Do you remember what that was? 239 00:15:55,550 --> 00:16:01,910 It was when the low crossed the high or vice versa, when the high crossed the low. 240 00:16:02,090 --> 00:16:05,990 So low should always be less than or equal to high. 241 00:16:06,260 --> 00:16:11,840 Remember when we had low and high, we're equal to two and we had the number six, but we were looking 242 00:16:11,840 --> 00:16:12,590 for four. 243 00:16:13,400 --> 00:16:19,280 We didn't find it, and what we did was we let high become one less than the mid. 244 00:16:20,000 --> 00:16:25,190 So instead of two, it was one and then suddenly now low was still two. 245 00:16:25,220 --> 00:16:29,120 Yet high was one and so high cross to the other side of low. 246 00:16:29,210 --> 00:16:30,080 That's problematic. 247 00:16:30,090 --> 00:16:31,370 That means that we need to stop. 248 00:16:31,370 --> 00:16:33,560 So that's going to be our stopping condition for the loop. 249 00:16:33,950 --> 00:16:40,250 And if that happens in a loop starts, we know that our item wasn't found because we went through everything 250 00:16:40,250 --> 00:16:44,930 until the point where low crossed high and there was nothing left for us to look at. 251 00:16:45,650 --> 00:16:51,740 So that's why many analysts say if low while low is less than or equal to high, we can loop. 252 00:16:52,880 --> 00:16:56,560 And then what I would do inside is immediately calculate me because we need to. 253 00:16:56,570 --> 00:16:59,180 That's the first thing we need to do is figure out our midpoint. 254 00:16:59,180 --> 00:17:06,260 I'm just going to call this middle and I'll say middle equals, and I'm going to say in parentheses, 255 00:17:06,280 --> 00:17:07,470 low plus high. 256 00:17:07,490 --> 00:17:08,890 So remember this formula? 257 00:17:08,900 --> 00:17:12,020 This was like the zero plus seven that we started out with, right? 258 00:17:12,920 --> 00:17:16,010 So low plus high divided by two. 259 00:17:17,090 --> 00:17:20,020 Now all we need to do is do our f checks, right? 260 00:17:20,030 --> 00:17:21,410 So we're going to say. 261 00:17:23,120 --> 00:17:34,000 Um, if, uh, the no, actually, it's just numb right now, so if none is greater than the index middle, 262 00:17:34,010 --> 00:17:37,100 so this is the actual thing that we're on right now, right? 263 00:17:37,760 --> 00:17:38,780 I can go back here. 264 00:17:39,110 --> 00:17:42,970 Let's go ahead and go back here. 265 00:17:42,980 --> 00:17:45,590 So this is like the middle, for example, right? 266 00:17:45,590 --> 00:17:46,580 This is the first medal. 267 00:17:46,580 --> 00:17:50,960 So we index middle would be nine in this case, right? 268 00:17:51,200 --> 00:17:53,180 And we're looking for four in this example. 269 00:17:53,180 --> 00:17:56,870 So we know that it would be left of nine. 270 00:17:57,230 --> 00:17:59,330 So I just want to point that out back to the example. 271 00:17:59,330 --> 00:18:05,060 So if none is greater than in, so that means that to the right, right, if it's greater, then we 272 00:18:05,060 --> 00:18:05,570 have medal. 273 00:18:06,140 --> 00:18:08,480 We're going to want to only consider stuff to the right. 274 00:18:08,490 --> 00:18:09,710 So what are we going to do? 275 00:18:09,950 --> 00:18:17,990 We're actually going to say Whoa, equals middle class one. 276 00:18:18,230 --> 00:18:19,610 And why are we going to do that? 277 00:18:19,850 --> 00:18:20,960 Well, let's think about it. 278 00:18:21,380 --> 00:18:23,960 This is the mid right minus three. 279 00:18:24,020 --> 00:18:26,870 The thing at mid position is nine. 280 00:18:27,470 --> 00:18:31,880 If we're looking, let's say not for four, let's say what we're looking for is greater than nine. 281 00:18:31,880 --> 00:18:33,380 Let's say it's twenty two. 282 00:18:33,380 --> 00:18:37,370 Again, if we're looking for twenty two, that's greater than nine. 283 00:18:37,370 --> 00:18:42,140 We know it's only going to be in this zone over here and we only want to care about this zone. 284 00:18:42,950 --> 00:18:46,610 Remember that what we did was we cut this, we cut all of this off. 285 00:18:46,610 --> 00:18:49,040 So what was our low it was for? 286 00:18:50,070 --> 00:18:52,470 Four is one more than three. 287 00:18:52,500 --> 00:19:01,530 So what we're doing is we're saying low equals middle plus one in the example, this is three plus one, 288 00:19:01,530 --> 00:19:03,370 which gives us four, right? 289 00:19:03,990 --> 00:19:09,540 So that's what we're doing if we want to look to the right where none is greater than what we're currently 290 00:19:09,540 --> 00:19:10,170 looking at. 291 00:19:11,220 --> 00:19:12,300 So that's what we're going to do. 292 00:19:12,310 --> 00:19:15,660 Low equals middle plus one and else f. 293 00:19:17,160 --> 00:19:17,550 All right. 294 00:19:17,610 --> 00:19:24,440 This is if none is less than the middle I had less than remittal. 295 00:19:24,450 --> 00:19:25,560 We're going to do the opposite. 296 00:19:25,560 --> 00:19:29,670 We're going to say high equals middle minus one. 297 00:19:30,060 --> 00:19:30,990 Why are we doing that? 298 00:19:31,050 --> 00:19:32,520 This is the perfect example. 299 00:19:32,520 --> 00:19:34,160 Four is less than nine, right? 300 00:19:34,170 --> 00:19:35,220 We're looking for four. 301 00:19:35,640 --> 00:19:38,160 It's not over here and it's not right here. 302 00:19:38,160 --> 00:19:39,560 So it's only over here. 303 00:19:39,570 --> 00:19:44,400 So what do we do to be able to have a new low and high? 304 00:19:45,120 --> 00:19:48,800 Well, we need to make high go from three to two. 305 00:19:50,310 --> 00:19:52,900 So what we're going to say is middle is three, right? 306 00:19:52,920 --> 00:19:55,890 Let's do one less than middle and that's our new high. 307 00:19:56,790 --> 00:19:57,120 Right? 308 00:19:58,910 --> 00:20:03,020 So we'll go ahead and we'll do that, we'll say high equals middle minus one. 309 00:20:03,650 --> 00:20:08,270 And if you're thinking, well, what about low, just think about this is the starting example, right? 310 00:20:08,270 --> 00:20:09,680 Low is zero. 311 00:20:09,890 --> 00:20:11,040 High is seven. 312 00:20:11,810 --> 00:20:13,070 Middle is three. 313 00:20:13,640 --> 00:20:15,500 We know we want to look to the left now. 314 00:20:15,510 --> 00:20:17,770 We're not going to move low from being zero. 315 00:20:17,780 --> 00:20:19,040 We're not going to change low. 316 00:20:19,040 --> 00:20:20,180 Low is zero, right? 317 00:20:20,600 --> 00:20:21,830 We only want to change high. 318 00:20:21,860 --> 00:20:27,950 So instead of seven, we're going to say now high is three minus one, which is two. 319 00:20:27,950 --> 00:20:30,080 So high gets this value. 320 00:20:30,290 --> 00:20:33,830 Low stay is zero, which is good because that's all we care about, right? 321 00:20:34,910 --> 00:20:35,780 We want this. 322 00:20:36,470 --> 00:20:40,870 So we we went from this to this now high and this example is two. 323 00:20:40,880 --> 00:20:43,910 So that is represented by this code right here. 324 00:20:44,420 --> 00:20:49,520 If NUM is less than what we're looking at, we're going to say hi to minus one. 325 00:20:49,790 --> 00:20:54,020 So what's the last condition in here that else? 326 00:20:54,920 --> 00:21:00,740 If something isn't greater then or less than the only other logical option is that it's equal to right. 327 00:21:01,160 --> 00:21:03,590 If it's equal to, we found it. 328 00:21:03,590 --> 00:21:07,130 So all we're going to do is just return true because we've found it. 329 00:21:07,130 --> 00:21:09,110 We know that we know that it's in there. 330 00:21:09,110 --> 00:21:12,150 Our function is a Boolean function, right? 331 00:21:12,560 --> 00:21:18,860 So this Boolean function is going to need to return true if we've seen our value. 332 00:21:18,860 --> 00:21:19,850 And what does that mean? 333 00:21:20,600 --> 00:21:28,130 It means that NUM is not greater than V middle or less than V middle number is equal to the middle. 334 00:21:28,190 --> 00:21:31,040 It's the thing that we're currently looking at is the same number. 335 00:21:31,220 --> 00:21:32,750 In that case, we return true. 336 00:21:33,470 --> 00:21:39,170 So we have all three of our cases represented here, and we have the code that updates the middle each 337 00:21:39,170 --> 00:21:39,950 time, right? 338 00:21:40,160 --> 00:21:41,450 So we have a new middle. 339 00:21:42,490 --> 00:21:50,680 Inside the IFS, we're actually updating our low and high correspondingly, so all that's left is that 340 00:21:50,680 --> 00:21:54,640 if we stop the loop right, if we make it all the way through the array. 341 00:21:55,710 --> 00:22:01,590 And what I mean by that is we keep having that happening and having cutting our array in half or a vector 342 00:22:01,590 --> 00:22:06,950 in half to the point where there's nothing left it in the loop will stop because low will be less so 343 00:22:06,990 --> 00:22:08,550 high will be less than low. 344 00:22:09,580 --> 00:22:12,100 And, you know, or low could be greater than high. 345 00:22:12,910 --> 00:22:14,500 Those high and lows will cross. 346 00:22:15,160 --> 00:22:21,580 And in that case, after the while loop, we're just going to say, well, we didn't find anything, 347 00:22:21,580 --> 00:22:23,410 so let's return false. 348 00:22:24,100 --> 00:22:24,460 All right. 349 00:22:26,980 --> 00:22:28,270 So just a little recap. 350 00:22:28,270 --> 00:22:30,070 We start out with low as zero always. 351 00:22:30,070 --> 00:22:32,260 We start out with high as the last element. 352 00:22:32,260 --> 00:22:32,770 Always. 353 00:22:32,830 --> 00:22:33,910 We start our loop. 354 00:22:33,910 --> 00:22:37,390 Our loop is based on the fact that low and high should never cross. 355 00:22:37,420 --> 00:22:39,370 Low should always be less than high. 356 00:22:39,700 --> 00:22:42,820 High shouldn't go less than low, low and go greater than high. 357 00:22:43,660 --> 00:22:45,460 If that happens, the loop will break. 358 00:22:45,460 --> 00:22:53,050 That means that we have keep chopping our list or our array or vector in half until we just didn't find 359 00:22:53,050 --> 00:22:54,370 anything, there was nothing left. 360 00:22:55,180 --> 00:23:00,130 So that's why there's a return false down there, this middle update to the middle each time to the 361 00:23:00,130 --> 00:23:05,530 actual middle of whatever between low and high by integer, divided by two. 362 00:23:06,070 --> 00:23:11,650 This if check is if we want to look to the right, if the number we're looking for is greater than what 363 00:23:11,650 --> 00:23:14,080 we're currently looking at inside the vector. 364 00:23:14,230 --> 00:23:15,430 We need to go to the right. 365 00:23:16,030 --> 00:23:17,880 That means we need to move low, right? 366 00:23:17,890 --> 00:23:21,910 We're not going to move high, but we're going to move low one right from the middle. 367 00:23:22,660 --> 00:23:27,160 Otherwise, if it's the opposite case, if the number we're looking for is less than what we're currently 368 00:23:27,160 --> 00:23:32,530 looking at in the vector, we need to change the high low stays the same. 369 00:23:32,530 --> 00:23:36,280 Yet high needs to be one less than what we're currently looking at, right? 370 00:23:36,280 --> 00:23:37,390 One less than the middle. 371 00:23:38,300 --> 00:23:43,400 Otherwise, the logical only other option is that it wasn't greater than or less than it was the exact 372 00:23:43,400 --> 00:23:45,200 same number, and we found it over time. 373 00:23:45,230 --> 00:23:45,470 True. 374 00:23:46,130 --> 00:23:47,450 So that's just a little recap. 375 00:23:47,630 --> 00:23:49,280 We have everything else set up here. 376 00:23:49,280 --> 00:23:52,240 So let's go ahead and save this and run it. 377 00:23:52,550 --> 00:23:53,840 Compile pilot, of course, first. 378 00:23:53,840 --> 00:23:55,370 So give us first binary search. 379 00:23:56,690 --> 00:24:03,110 So I'll just call this that the researcher out. 380 00:24:04,960 --> 00:24:07,570 All right, so middle was not declared in this scope. 381 00:24:08,290 --> 00:24:09,640 Let's see what that problem is. 382 00:24:10,900 --> 00:24:13,450 I think it's just because I put med or something like that, probably. 383 00:24:14,390 --> 00:24:16,980 So at the. 384 00:24:20,120 --> 00:24:21,980 Oops and middle. 385 00:24:22,940 --> 00:24:28,970 Yeah, so what I'll do is, I'll just put it know right here and then I can change it in there. 386 00:24:32,010 --> 00:24:35,850 Yeah, this so this is the problem right here, exactly what I was talking about, so let me run this 387 00:24:35,850 --> 00:24:36,930 again, clear it and run it. 388 00:24:36,930 --> 00:24:45,360 So it says in C++ 98, my work must be initialized by a constructor, not by an initialization list, 389 00:24:45,360 --> 00:24:48,030 which is what this syntax is right here. 390 00:24:48,600 --> 00:24:55,470 So what I'm going to do since I have an older version of C++ running by default here is I am going to 391 00:24:55,470 --> 00:25:00,670 add a little compiler flag where I go hyphen hyphen study. 392 00:25:00,690 --> 00:25:06,360 So a standard equals C++ 11 eight. 393 00:25:06,990 --> 00:25:09,390 So I run that again and no problems. 394 00:25:11,520 --> 00:25:12,570 I run this list. 395 00:25:12,570 --> 00:25:14,360 Enter a number to be searched in the vector. 396 00:25:14,370 --> 00:25:17,850 Well, we have our numbers right here above us thanks to the error, right? 397 00:25:17,860 --> 00:25:19,350 So let's search for. 398 00:25:20,680 --> 00:25:26,550 Let's search for forty four, so we say forty four says we found the number forty four and the vector. 399 00:25:26,590 --> 00:25:27,430 Let's run again. 400 00:25:27,430 --> 00:25:28,960 Let's search for like eighty eight. 401 00:25:29,530 --> 00:25:31,800 We did not find the number eighty eight in the vector. 402 00:25:31,810 --> 00:25:32,590 Let's run it again. 403 00:25:32,590 --> 00:25:33,880 Let's search for three. 404 00:25:34,810 --> 00:25:36,340 We found the number three. 405 00:25:36,370 --> 00:25:37,240 Let's run it again. 406 00:25:37,240 --> 00:25:43,720 With social one, we found the number one inch or some crazy number like this or something like that. 407 00:25:44,350 --> 00:25:48,820 We did not find the number three thousand fifty four, so you can see that this works pretty well. 408 00:25:51,130 --> 00:25:58,060 So that is actually all I have to say about binary search, it is really good, though it that is a 409 00:25:58,060 --> 00:25:59,680 really fast algorithm. 410 00:25:59,860 --> 00:26:02,440 I mentioned that it runs in logarithmic time. 411 00:26:02,590 --> 00:26:03,960 You don't have to look too much into that. 412 00:26:03,970 --> 00:26:11,050 We're going to talk about what logarithmic time, linear time and even other times are when we go over 413 00:26:11,050 --> 00:26:16,900 runtime complexity, time, complexity and general, that's in the algorithm section of the course, 414 00:26:17,470 --> 00:26:19,330 the data structures and our rhythm section. 415 00:26:19,720 --> 00:26:25,030 I'm putting that off because it is slightly more complex topic and we actually will get into analyzing 416 00:26:25,030 --> 00:26:27,520 these things mathematically in that portion of the course. 417 00:26:27,910 --> 00:26:33,220 We'll do a brief introduction and then we will go over a in-depth analysis of algorithms as well. 418 00:26:34,030 --> 00:26:34,450 OK. 419 00:26:34,870 --> 00:26:42,940 So if it's possible to have a sorted array, if you're a sorted, you should use binary searches much 420 00:26:42,940 --> 00:26:44,400 faster than linear search. 421 00:26:44,410 --> 00:26:49,210 So just take that as a note, and I will see you in the next lecture.