Evaluating Binary Search

The algorithm John used, linear search, seemed familiar to us. 0:00 And you could understand it because it's how most of us search for 0:03 things in real life anyway. 0:06 Britney's approach, on the other hand, 0:08 got results quickly, but it was a bit harder to understand. 0:10 So let's break it down. 0:13 [SOUND] Just like John's approach, Britney started with a series of values, or 0:14 list of numbers, as her input. 0:18 Where John just started at the beginning of the list and searched sequentially, 0:20 Britney's strategy is to always start in the middle of the range. 0:25 From there, she asks a comparison question, 0:28 is the number in the middle of the range equal to the answer she's looking for? 0:31 And if it's not, is it greater than or less than the answer? 0:36 If it's greater than, 0:39 she can eliminate all the values less than the one she's currently evaluating. 0:41 If it's lesser than the answer, 0:46 she can eliminate all the values greater than the one she's currently evaluating. 0:47 With the range of values that she's left over with, 0:52 she repeats this process until she arrives at the answer. 0:55 [SOUND] Let's visualize how she did this by looking at Round 3. 0:58 [SOUND] In Round 3, the number of values in the range was 100. 1:03 The answer was 5. 1:06 The bar here represents the range of values, 1 on the left, 100 on 1:07 the right and this pointer represents the value Britney chooses to evaluate. 1:11 So she starts in the middle at 50, she asks is it equal to the answer? 1:16 I say it's too high. 1:21 So this tells her that the value she is evaluating is greater than our target 1:22 value. 1:27 Which means there's no point in searching any of the values to the right of 50, 1:27 that is values greater than 50 in this range. 1:32 So she can discard those values altogether. 1:35 [SOUND] She only has to consider values from 1 to 50 now. 1:38 [SOUND] The beauty of this strategy, and 1:42 the reason why Britney was able to find the answer in such few turns, 1:44 is that with every value she evaluates, she can discard half of the current range. 1:48 On her second turn, [SOUND] she picks the value in the middle of the current range, 1:53 which is 25. 1:57 She asks the same question. 1:58 I say that the value is too high again. 2:00 And this tells her that she can discard everything greater than 25. 2:03 [SOUND] And the range of value drops from 1 to 25. 2:07 Again, she evaluates the number in the middle, roughly. 2:10 So that'd be 13, here. 2:13 I tell her, this is still too high. 2:15 She discards the values greater, moves to value 7, which is still too high. 2:17 Then she moves to 4, which is now too low. 2:21 She can discard everything less than 4, which leaves the numbers 4 through 7. 2:24 Here, she picks 6, which is too high, which only leaves one value, 5. 2:29 This seems like a lot of work. 2:34 But being able to get rid of half the values with each turn 2:36 is what makes this algorithm much more efficient. 2:40 Now, there's one subtlety to using binary search, and 2:43 you might have caught on to this. 2:46 For this search method to work, as we've mentioned, the values need to be sorted. 2:47 [SOUND] With linear search, it doesn't matter if the values are sorted. 2:52 Since a linear search algorithm just progresses sequentially, 2:55 checking every element in the list. 2:59 If the target value exists in the list, it will be found. 3:02 Let's say this range of values, 1 to 100, was unsorted. 3:05 Britney would start at the middle with something like 14 and 3:09 ask if this value was too low or too high? 3:12 I say it's too high so she discards everything less than 14. 3:15 Now, this example starts to fall apart here, because well, 3:19 Brittany knows what numbers are less than 14 and greater than 1. 3:22 She doesn't need an actual range of values to solve this. 3:26 A computer, however, does need that. 3:29 Remember, search algorithms are run against lists containing all sorts 3:31 of data. 3:36 It's not always just a range of values containing numbers. 3:37 In a real use case of binary search, which we're going to implement in a bit. 3:39 The algorithm wouldn't return the target value because we already know 3:44 that it's a search algorithm. 3:48 So we're providing something to search for. 3:50 Instead, what it returns is the position in the list that the target occupies. 3:52 Without the list being sorted, 3:56 a binary search algorithm will discard all the values to the left of 14 which over 3:58 here could include the position where our target value is. 4:03 Eventually we get a result back saying the target value doesn't exist in the list 4:06 which is inaccurate. 4:10 Earlier when defining linear simple search I said that the input was a list of 4:12 values and the output was the target value or 4:17 more specifically the position of the target value in the list. 4:19 So at binary search there's also that pre-condition the input list must be 4:24 sorted. 4:28 So let's formally define binary search. 4:29 First the input a sorted list of values. 4:31 The output, 4:35 the position in the list of the target value we're searching for, [SOUND] or 4:35 some sort of values indicate that the target does not exist in the list. 4:40 Remember our guidelines for defining an algorithm? 4:44 Let me put those up again really quick. 4:47 The steps in the algorithm need to be in a specific order. 4:48 The steps also need to be very distinct. 4:52 The algorithms should produce a result and 4:54 finally the algorithms should complete in a finite amount of time. 4:57 Let’s use those to define this algorithm. 5:01 Step one, [SOUND] we determine the middle position of the sorted list. 5:04 Step two, we compare the element in the middle position to the target element. 5:07 Step three, if the elements match, we return the middle position and end. 5:12 [SOUND] If they don't match, in step four, we check whether the element in 5:17 the middle position is smaller than the target element. 5:21 [SOUND] If it is, then we go back to step two, with a new list that goes from 5:24 the middle position of the current list to the end of the current list. 5:29 [SOUND] In step five, if the element in the middle position is greater than 5:33 the target element, then again [SOUND] we go back to step two. 5:37 With a new list that goes to the start of the current list to the middle 5:40 of the current list. 5:44 [SOUND] We repeat this process until the target element is found. 5:45 Or until a sub-list contains only one element. 5:49 If that single element sub-list does not match the target elements, 5:52 then we end the algorithm. 5:57 Indicating that the element does not exist in the list. 5:59 Okay, so 6:02 that is the magic behind how Britney managed to solve around much faster. 6:02 In the next video let's talk about the efficiency of binary search 6:07