1 00:00:04,150 --> 00:00:08,830 In the last video, we completed the challenge to fix the guessing game so it 2 00:00:08,830 --> 00:00:12,400 used the while loop, but I also finished by saying that we should need ten 3 00:00:12,400 --> 00:00:16,450 guesses or less, to guess any number from 1 to 1,000, which we've currently had our 4 00:00:16,450 --> 00:00:21,520 program set to. So I want to talk about that a bit more. The thing is, trying to 5 00:00:21,520 --> 00:00:24,440 guess a number between 1 and 1000 is difficult - 6 00:00:24,440 --> 00:00:29,290 the guess will be wrong 999 times out of a thousand. What if we could narrow that 7 00:00:29,290 --> 00:00:33,550 range down, so we're only guessing a number from 500 numbers? That improves 8 00:00:33,550 --> 00:00:39,219 our chances - now we'd only be wrong 499 times. If we reduce that further to 250 9 00:00:39,220 --> 00:00:45,740 numbers, we'd only be wrong 249 times. So that's how a binary search works. 10 00:00:45,740 --> 00:00:49,500 When you have an ordered set of data to search through, you can split the data in 11 00:00:49,510 --> 00:00:53,649 half each time. Guessing a number is very much like searching for a value in an 12 00:00:53,649 --> 00:00:57,730 ordered set of data. Of course, we know that the value you're guessing does 13 00:00:57,730 --> 00:01:04,140 exist. That simplifies things slightly, but the basic steps are the same. 14 00:01:04,140 --> 00:01:08,800 So our first guess is 500, which is half of 1,000. So if we have to guess lower, 15 00:01:08,800 --> 00:01:15,340 we halve 500 and guess 250. For the third guess, we halve 250 and guess 125. 16 00:01:15,340 --> 00:01:20,710 Halving 125 gives a floating point value, 62.5. Now we're only guessing whole numbers, 17 00:01:20,710 --> 00:01:25,000 and we've seen that Pythons integer division rounds down. The middle column 18 00:01:25,000 --> 00:01:28,900 shows the integer values we'd use, instead of the floating point values 19 00:01:28,900 --> 00:01:34,330 that we get when dividing by 2. By continuing to half the range of values 20 00:01:34,330 --> 00:01:41,500 that we have to guess, we can guess any number from 1 to 1000 in a maximum of 10 guesses. 21 00:01:41,500 --> 00:01:45,000 Now the table only shows 9 guesses. It's showing what happens when 22 00:01:45,000 --> 00:01:51,140 we have to guess lower each time, to show how the range of values halves with each guess. 23 00:01:51,140 --> 00:01:54,940 If the answer was 2, we'd have to have another higher guess, after we 24 00:01:54,940 --> 00:01:59,200 guessed 1. That would give us 10 guesses, which is the most we'd need in order to 25 00:01:59,200 --> 00:02:04,000 guess a number from 1 to 1000. Now we may need fewer guesses, but we shouldn't need 26 00:02:04,000 --> 00:02:09,639 more than 10. Of course, sometimes we'll have to get higher, not lower, but the 27 00:02:09,639 --> 00:02:12,340 principle's the same and you saw that in the previous video, 28 00:02:12,340 --> 00:02:17,019 when I started doing binary searches to find the correct answer. When guessing 29 00:02:17,020 --> 00:02:21,820 higher, we use the upper half of the range, instead of the lower half. 30 00:02:21,820 --> 00:02:25,060 Our first case would still be 500. For the second guess, we'd split the 31 00:02:25,060 --> 00:02:30,550 range from 500 to 1000, giving 750. If we had to guess higher again, the third 32 00:02:30,550 --> 00:02:36,010 guess allows the range from 750 to 1000 to give 875. With each guess, the range of 33 00:02:36,010 --> 00:02:40,240 numbers we have to guess is halved. In reality, 34 00:02:40,240 --> 00:02:44,200 we'll use a combination of higher and lower guesses. For example, let's say the 35 00:02:44,200 --> 00:02:51,370 answer was 998. After our 9th guess, 999, we'd have to guess lower. The range of 36 00:02:51,370 --> 00:02:58,600 numbers to guess is between 997, our 8th guess, and 999. So we'd guess 998, and 37 00:02:58,600 --> 00:03:04,380 get it right with the 10th guess. Alright so let's work through a real example. 38 00:03:04,380 --> 00:03:07,120 To keep the slides manageable, we're going to be guessing a number 39 00:03:07,120 --> 00:03:11,200 between 1 and 10. We should be able to do that within four guesses. So let's say 40 00:03:11,200 --> 00:03:16,060 that the answer is 7. We start off by guessing the mid-point between the low 41 00:03:16,060 --> 00:03:21,200 and high values. The formula we use is: low plus, and in parentheses, high minus low 42 00:03:21,200 --> 00:03:24,070 integer divide by 2. So putting our 43 00:03:24,070 --> 00:03:28,780 low and high values in the formula, we get 1 plus parentheses 10 - 1 integer 44 00:03:28,780 --> 00:03:33,610 divide by 2, which is 1 plus 4 giving 5. Remember that integer division rounds 45 00:03:33,610 --> 00:03:40,660 down, and 9 integer division 2 is 4, so 5 is our first guess. We're told to guess higher. 46 00:03:40,660 --> 00:03:44,780 That means the answer must lie somewhere between 6 and 10. We know it's greater 47 00:03:44,800 --> 00:03:49,640 than 5, so the lowest it can be is 6. That's our new low value for the range. 48 00:03:49,640 --> 00:03:54,280 The mid-point now becomes 6 plus 10 minus 6 in parentheses integer divide by 2 49 00:03:54,280 --> 00:03:58,660 which is 8, so therefore our next guest will be 8. 50 00:03:58,660 --> 00:04:03,240 We're told to guess lower. That means the answer must lie somewhere between 6 and 7. 51 00:04:03,240 --> 00:04:07,420 We know the answer's less than 8, so the largest it can be is 7. 52 00:04:07,420 --> 00:04:11,620 That's a new high value for the range. The mid-point now becomes 6 plus 53 00:04:11,620 --> 00:04:15,300 parenthesis 7 minus 6 integer divide by 2, 54 00:04:15,300 --> 00:04:20,500 which is 6 - integer division does round down. So our third guess would be 6. 55 00:04:20,500 --> 00:04:24,740 7 is greater than 6, so we're told to guess higher. Our low value now 56 00:04:24,750 --> 00:04:28,740 becomes 7, the same as the high value. At this point, a human will guess 7 57 00:04:28,740 --> 00:04:33,210 right away. The computer has to do the calculation first. The mid-point now 58 00:04:33,210 --> 00:04:37,580 becomes 7 plus, and in parentheses, 7 minus 7 integer divide by 2 59 00:04:37,580 --> 00:04:43,040 which is seven. So our fourth guess will be 7, and we get the correct answer. 60 00:04:43,040 --> 00:04:47,160 So each incorrect guess halves the range of numbers that we have to guess. 61 00:04:47,160 --> 00:04:52,720 That's why this technique is known as a binary search, or binary chop. 62 00:04:54,069 --> 00:04:58,869 The binary search algorithm is the most efficient way of finding an item in an 63 00:04:58,869 --> 00:05:02,949 ordered list. It forms the basis for the data structures that database 64 00:05:02,949 --> 00:05:08,139 programs, such as SQLite and Oracle, use for storing the database keys. 65 00:05:08,140 --> 00:05:12,420 And that allows for very fast searching of the data. Alright so in the next video, 66 00:05:12,420 --> 00:05:16,000 we'll write the code to guess a number using a binary chop. 67 00:05:16,000 --> 00:05:19,100 See you in the next video.