1 00:00:00,000 --> 00:00:03,514 The algorithm John used, linear search, seemed familiar to us. 2 00:00:03,514 --> 00:00:06,739 And you could understand it because it's how most of us search for 3 00:00:06,739 --> 00:00:08,155 things in real life anyway. 4 00:00:08,155 --> 00:00:10,280 Britney's approach, on the other hand, 5 00:00:10,280 --> 00:00:13,298 got results quickly, but it was a bit harder to understand. 6 00:00:13,298 --> 00:00:14,324 So let's break it down. 7 00:00:14,324 --> 00:00:18,760 [SOUND] Just like John's approach, Britney started with a series of values, or 8 00:00:18,760 --> 00:00:20,558 list of numbers, as her input. 9 00:00:20,558 --> 00:00:25,156 Where John just started at the beginning of the list and searched sequentially, 10 00:00:25,156 --> 00:00:28,955 Britney's strategy is to always start in the middle of the range. 11 00:00:28,955 --> 00:00:31,703 From there, she asks a comparison question, 12 00:00:31,703 --> 00:00:36,359 is the number in the middle of the range equal to the answer she's looking for? 13 00:00:36,359 --> 00:00:39,530 And if it's not, is it greater than or less than the answer? 14 00:00:39,530 --> 00:00:41,001 If it's greater than, 15 00:00:41,001 --> 00:00:46,007 she can eliminate all the values less than the one she's currently evaluating. 16 00:00:46,007 --> 00:00:47,705 If it's lesser than the answer, 17 00:00:47,705 --> 00:00:52,022 she can eliminate all the values greater than the one she's currently evaluating. 18 00:00:52,022 --> 00:00:55,135 With the range of values that she's left over with, 19 00:00:55,135 --> 00:00:58,617 she repeats this process until she arrives at the answer. 20 00:00:58,617 --> 00:01:03,077 [SOUND] Let's visualize how she did this by looking at Round 3. 21 00:01:03,077 --> 00:01:06,335 [SOUND] In Round 3, the number of values in the range was 100. 22 00:01:06,335 --> 00:01:07,590 The answer was 5. 23 00:01:07,590 --> 00:01:11,640 The bar here represents the range of values, 1 on the left, 100 on 24 00:01:11,640 --> 00:01:16,185 the right and this pointer represents the value Britney chooses to evaluate. 25 00:01:16,185 --> 00:01:21,109 So she starts in the middle at 50, she asks is it equal to the answer? 26 00:01:21,109 --> 00:01:22,664 I say it's too high. 27 00:01:22,664 --> 00:01:27,358 So this tells her that the value she is evaluating is greater than our target 28 00:01:27,358 --> 00:01:27,887 value. 29 00:01:27,887 --> 00:01:32,725 Which means there's no point in searching any of the values to the right of 50, 30 00:01:32,725 --> 00:01:35,583 that is values greater than 50 in this range. 31 00:01:35,583 --> 00:01:38,267 So she can discard those values altogether. 32 00:01:38,267 --> 00:01:42,271 [SOUND] She only has to consider values from 1 to 50 now. 33 00:01:42,271 --> 00:01:44,532 [SOUND] The beauty of this strategy, and 34 00:01:44,532 --> 00:01:48,435 the reason why Britney was able to find the answer in such few turns, 35 00:01:48,435 --> 00:01:53,252 is that with every value she evaluates, she can discard half of the current range. 36 00:01:53,252 --> 00:01:57,849 On her second turn, [SOUND] she picks the value in the middle of the current range, 37 00:01:57,849 --> 00:01:58,734 which is 25. 38 00:01:58,734 --> 00:02:00,646 She asks the same question. 39 00:02:00,646 --> 00:02:03,183 I say that the value is too high again. 40 00:02:03,183 --> 00:02:07,150 And this tells her that she can discard everything greater than 25. 41 00:02:07,150 --> 00:02:10,179 [SOUND] And the range of value drops from 1 to 25. 42 00:02:10,179 --> 00:02:13,479 Again, she evaluates the number in the middle, roughly. 43 00:02:13,479 --> 00:02:15,711 So that'd be 13, here. 44 00:02:15,711 --> 00:02:17,158 I tell her, this is still too high. 45 00:02:17,158 --> 00:02:21,922 She discards the values greater, moves to value 7, which is still too high. 46 00:02:21,922 --> 00:02:24,885 Then she moves to 4, which is now too low. 47 00:02:24,885 --> 00:02:29,618 She can discard everything less than 4, which leaves the numbers 4 through 7. 48 00:02:29,618 --> 00:02:34,473 Here, she picks 6, which is too high, which only leaves one value, 5. 49 00:02:34,473 --> 00:02:36,819 This seems like a lot of work. 50 00:02:36,819 --> 00:02:40,183 But being able to get rid of half the values with each turn 51 00:02:40,183 --> 00:02:43,274 is what makes this algorithm much more efficient. 52 00:02:43,274 --> 00:02:46,169 Now, there's one subtlety to using binary search, and 53 00:02:46,169 --> 00:02:47,868 you might have caught on to this. 54 00:02:47,868 --> 00:02:52,466 For this search method to work, as we've mentioned, the values need to be sorted. 55 00:02:52,466 --> 00:02:55,930 [SOUND] With linear search, it doesn't matter if the values are sorted. 56 00:02:55,930 --> 00:02:59,916 Since a linear search algorithm just progresses sequentially, 57 00:02:59,916 --> 00:03:02,168 checking every element in the list. 58 00:03:02,168 --> 00:03:05,379 If the target value exists in the list, it will be found. 59 00:03:05,379 --> 00:03:09,142 Let's say this range of values, 1 to 100, was unsorted. 60 00:03:09,142 --> 00:03:12,783 Britney would start at the middle with something like 14 and 61 00:03:12,783 --> 00:03:15,174 ask if this value was too low or too high? 62 00:03:15,174 --> 00:03:19,128 I say it's too high so she discards everything less than 14. 63 00:03:19,128 --> 00:03:22,595 Now, this example starts to fall apart here, because well, 64 00:03:22,595 --> 00:03:26,407 Brittany knows what numbers are less than 14 and greater than 1. 65 00:03:26,407 --> 00:03:29,388 She doesn't need an actual range of values to solve this. 66 00:03:29,388 --> 00:03:31,979 A computer, however, does need that. 67 00:03:31,979 --> 00:03:36,452 Remember, search algorithms are run against lists containing all sorts 68 00:03:36,452 --> 00:03:37,033 of data. 69 00:03:37,033 --> 00:03:39,697 It's not always just a range of values containing numbers. 70 00:03:39,697 --> 00:03:44,372 In a real use case of binary search, which we're going to implement in a bit. 71 00:03:44,372 --> 00:03:48,499 The algorithm wouldn't return the target value because we already know 72 00:03:48,499 --> 00:03:50,332 that it's a search algorithm. 73 00:03:50,332 --> 00:03:52,253 So we're providing something to search for. 74 00:03:52,253 --> 00:03:56,937 Instead, what it returns is the position in the list that the target occupies. 75 00:03:56,937 --> 00:03:58,721 Without the list being sorted, 76 00:03:58,721 --> 00:04:03,280 a binary search algorithm will discard all the values to the left of 14 which over 77 00:04:03,280 --> 00:04:06,602 here could include the position where our target value is. 78 00:04:06,602 --> 00:04:10,955 Eventually we get a result back saying the target value doesn't exist in the list 79 00:04:10,955 --> 00:04:12,180 which is inaccurate. 80 00:04:12,180 --> 00:04:17,109 Earlier when defining linear simple search I said that the input was a list of 81 00:04:17,109 --> 00:04:19,958 values and the output was the target value or 82 00:04:19,958 --> 00:04:24,137 more specifically the position of the target value in the list. 83 00:04:24,137 --> 00:04:28,683 So at binary search there's also that pre-condition the input list must be 84 00:04:28,683 --> 00:04:29,258 sorted. 85 00:04:29,258 --> 00:04:31,485 So let's formally define binary search. 86 00:04:31,485 --> 00:04:35,036 First the input a sorted list of values. 87 00:04:35,036 --> 00:04:35,806 The output, 88 00:04:35,806 --> 00:04:40,216 the position in the list of the target value we're searching for, [SOUND] or 89 00:04:40,216 --> 00:04:44,420 some sort of values indicate that the target does not exist in the list. 90 00:04:44,420 --> 00:04:47,482 Remember our guidelines for defining an algorithm? 91 00:04:47,482 --> 00:04:48,980 Let me put those up again really quick. 92 00:04:48,980 --> 00:04:52,627 The steps in the algorithm need to be in a specific order. 93 00:04:52,627 --> 00:04:54,792 The steps also need to be very distinct. 94 00:04:54,792 --> 00:04:57,209 The algorithms should produce a result and 95 00:04:57,209 --> 00:05:01,044 finally the algorithms should complete in a finite amount of time. 96 00:05:01,044 --> 00:05:04,022 Let’s use those to define this algorithm. 97 00:05:04,022 --> 00:05:07,644 Step one, [SOUND] we determine the middle position of the sorted list. 98 00:05:07,644 --> 00:05:12,499 Step two, we compare the element in the middle position to the target element. 99 00:05:12,499 --> 00:05:17,964 Step three, if the elements match, we return the middle position and end. 100 00:05:17,964 --> 00:05:21,873 [SOUND] If they don't match, in step four, we check whether the element in 101 00:05:21,873 --> 00:05:24,913 the middle position is smaller than the target element. 102 00:05:24,913 --> 00:05:29,173 [SOUND] If it is, then we go back to step two, with a new list that goes from 103 00:05:29,173 --> 00:05:33,379 the middle position of the current list to the end of the current list. 104 00:05:33,379 --> 00:05:37,146 [SOUND] In step five, if the element in the middle position is greater than 105 00:05:37,146 --> 00:05:40,317 the target element, then again [SOUND] we go back to step two. 106 00:05:40,317 --> 00:05:44,595 With a new list that goes to the start of the current list to the middle 107 00:05:44,595 --> 00:05:45,957 of the current list. 108 00:05:45,957 --> 00:05:49,543 [SOUND] We repeat this process until the target element is found. 109 00:05:49,543 --> 00:05:52,690 Or until a sub-list contains only one element. 110 00:05:52,690 --> 00:05:57,544 If that single element sub-list does not match the target elements, 111 00:05:57,544 --> 00:05:59,442 then we end the algorithm. 112 00:05:59,442 --> 00:06:02,269 Indicating that the element does not exist in the list. 113 00:06:02,269 --> 00:06:02,902 Okay, so 114 00:06:02,902 --> 00:06:07,822 that is the magic behind how Britney managed to solve around much faster. 115 00:06:07,822 --> 00:06:12,991 In the next video let's talk about the efficiency of binary search