Recursive Binary Search13:07 with Pasan Premaratne
There's more than one way to implement the binary search algorithm and in this video we take a look at a new concept called recursion.
I'm going to create a new file. 0:00 As always File > New File, and 0:02 we'll name this recursive_binary_search.py. 0:06 Okay, so I'm going to add our new implementation here, so 0:14 that we don't get rid of that first implementation we wrote. 0:17 Let's call this new function recursive_binary_search. 0:20 Unlike our previous implementation, 0:24 this version is going to behave slightly differently in that it won't return 0:26 the index value of the target element if it exists. 0:31 Instead, it will just return a true value if it exist, and a false if it doesn't. 0:34 So recursive_binary_search, and like before, 0:38 this is going to take a list, it accepts a list, 0:43 and a target to look for in that list. 0:48 We'll start at the body of the function by considering what happens if an empty 0:52 list is passed in. 0:57 In that case, we would return false. 0:58 So let's say if the length of the list, which is one way to figure it out if it's 1:00 empty, if it's equal to 0, then we'll return False. 1:04 Now you might be thinking that in the previous version of binary_search, 1:08 we didn't care if the list was empty. 1:12 Well, we actually did, but in a roundabout sort of way. 1:15 So in the previous version of binary_search, our function had a loop, 1:18 and that loop condition was true when first was less than or equal to last. 1:23 So as long as it's less than or equal to last, we continue the loop. 1:28 Now if we have an empty list, then first is greater than last, and 1:32 the loop would never execute and we return none at the bottom. 1:36 So this is the same logic we're implementing here, 1:40 we're just doing it in a slightly different way. 1:43 If the list is not empty, we'll implement an else clause. 1:45 Now here we'll calculate the midpoint by dividing 1:50 the length of the list by 2 and rounding down. 1:54 Again, there's no use of first and last here. 1:58 So say len(list), and then using the floor division operator we'll divide that by 2. 2:01 If the value at the midpoint, which we'll check by saying if list 2:08 using subscript notation, we'll say midpoint as the index. 2:13 Now if this value at the midpoint is the same as the target, 2:18 then we'll go ahead and return True. 2:23 So far, this is more or less the same except for the value that were returning. 2:26 Let me actually get rid of all that. 2:33 Okay, all right, so if this isn't the case, let's implement an else clause. 2:38 Now here we have two situations. 2:43 So first, if the value at the midpoint is less than the target, 2:44 so if value at midpoint is less than the target, 2:50 then we're gonna do something new, we're going to call this function again. 2:54 This recursive_binary_search function that we're in the process of defining, 3:02 we're gonna call that again, and 3:06 we're going to give it the portion of the list that we want to focus on. 3:08 In the previous version of binary search, 3:12 we moved the first value to point to the value after the midpoint. 3:15 Now here, we're going to create a new list using what is called a slice operation, 3:20 and create a sublist that starts at midpoint plus one, and 3:26 goes all the way to the end. 3:29 We're going to specify the same target as a search target, 3:31 and when this function call is done we'll return the value. 3:35 So we'll say return. 3:39 The return is important. 3:40 Then we'll call this function again, recursive_binary_search. 3:42 And this function takes a list. 3:48 And here, we are going to use that subscript notation to perform a slice 3:49 operation by using two indexes, A start and an end. 3:54 So we'll say our new list that we're passing in, 3:57 needs to start at midpoint + 1. 4:00 And then, we'll go all the way to the end, and 4:02 this is a Python syntatic sugar, so to speak. 4:06 If I don't specify an end index, Python knows to just go all the way to the end. 4:09 All right, so this is our new list that we're working with. 4:13 And we need a target. 4:16 We'll just pass it through. 4:17 If you're confused bear with me. 4:19 Just like before, we'll visualize this at the end. 4:21 Okay, we have another else case here. 4:24 And this is a scenario where the value at the midpoint is greater than the target. 4:26 Which means we only care about the values in the list from the start going up to 4:31 the midpoint. 4:36 Now in this case as well, we're going to call the binary_search function again and 4:37 specify a new list to work with. 4:41 This time, the list is going to start at the beginning, and 4:43 then go all the way up to the midpoint. 4:46 So it looks the same. 4:48 We'll say return recursive_binary_search. 4:49 We're gonna pass in a list here. 4:55 So if we just put a colon here, without a start index, Python knows to 4:57 start at the beginning and we're going to go all the way up to the midpoint. 5:02 The target here is the same. 5:08 And this is our new binary_search function, so let's see if this works. 5:09 Actually, yes. 5:15 Down here, we'll make some space and I'll define a verify function. 5:16 We're now gonna copy/paste the previous one because we're not returning none or 5:22 an integer here. 5:26 So we'll verify the result that we pass in and we'll say print("Target found: and 5:27 this is just going to say true or false, whether we found it, okay? 5:33 So like before, we need a numbers list. 5:38 And we'll do something like 1, 2, 3, 4, all the way up to 8, okay? 5:41 And now let's test this out. 5:46 So we'll call our recursive_binary_search function. 5:48 And we'll pass in the numbers list. 5:54 And the target here is 12. 5:58 We're gonna verify this. 6:01 Verify the result, make sure it works. 6:03 And then we'll call it again. 6:05 This time making sure that we give it a target that is actually in the list. 6:07 So here we'll say 6 and we'll verify this again. 6:11 Make sure you hit Cmd + S to save. 6:16 And then in the console below, 6:18 we're gonna type out Python recursive_binary_search.py. 6:21 Run it and you'll see that we've verified that search works. 6:26 While we can't verify the index position of the target value, 6:30 which is a modification to how our algorithm works, we can 6:33 guarantee by running across all valid inputs that search works as intended. 6:37 So why write a different search algorithm here, a different binary search algorithm? 6:42 And what's the different between these two implementations anyway? 6:48 The different lies in these last four lines of code that you see here. 6:51 We did something unusual here. 6:58 Now, before we get into this, a small word of advice, this is a confusing topic, 7:00 and people get confused by it all the time. 7:05 Don't worry, that doesn't make you any less of a programmer. 7:08 In fact, I have trouble with it often, and always look it up, 7:12 including when I made this video. 7:15 This version of binary search is a recursive binary search. 7:17 A recursive function is one that calls itself. 7:21 This is hard for 7:25 people to grasp sometimes because there's few easy analogies that make sense. 7:26 But you can think of it in sort of this way. 7:31 So let's say you have this book that contains answers to multiplication 7:33 problems. 7:37 You're working on a problem and you look up an answer. 7:38 In the book, the answer for your problem says add 10 to the answer for problem 52. 7:41 Okay, so you look up problem 52 and there it says, 7:49 add 12 to the answer for problem 85. 7:53 Well, then you go and look up the answer to problem 85 and finally, 7:57 instead of redirecting you somewhere else, that answers says 10. 8:00 So you take that 10 and then you go back to problem 52. 8:04 Because remember, the answer for 8:08 problem 52 was to add 12 to the answer for problem 85. 8:10 So you take that 10, and then you now have the answer to problem 85, 8:14 so you add 10 to 12 to get 22. 8:19 Then you go back to your original problem where it said to add 10 to the answer for 8:22 problem 52. 8:27 So you add 10 to 22 and you get 32 to end up with your final answer. 8:28 So that's a weird way of doing it but this is an example of recursion. 8:32 The solution to your first look up in the book was the value obtained by another 8:36 look up in the same book, which was followed by yet 8:41 another look up in the same book. 8:44 The book told you to check the book until you arrived at some base value. 8:46 Our function works in a similar manner. 8:51 So let's visualize this with an example of list. 8:53 Like before, we have a 9 element list here, with values 0 through 8. 8:57 The target we're searching for is the value 8. 9:02 We'll check if the list is empty by calling len on it. 9:05 This list is not empty, so we go to the else clause. 9:09 Next we calculated the midpoint, 9/2 = 4.5, 9:12 rounded down is 4, so our first midpoint value is 4. 9:16 We'll perform our first check, is the value at the midpoint equal to the target? 9:20 Not true, so we go to our else clause. 9:25 We'll perform another check here. 9:28 Is the value at the midpoint less than the target. 9:30 Now in our case, this is true. 9:33 Earlier when we evaluated this condition, we simply changed the value of first. 9:35 Here we're going to call the recursive binary search function again and 9:40 give it a new list to work with. 9:44 The list starts at midpoint plus one. 9:46 So at index position 5, all the way to the end. 9:49 Notice that this call to recursive binary search, 9:52 inside a recursive binary search includes a return statement. 9:56 This is important and we'll come back to that in a second. 10:01 So now we're back at the top of a new call to recursive binary search 10:04 with effectively a new list, although technically, 10:09 just a sub list of the first one. 10:13 The list here contains the numbers 6, 7, and 8. 10:15 Starting with the first check, the list is not empty, so we move to the else. 10:20 The midpoint in this case, length of the list, 3 divided by 2 rounded down is 1. 10:25 Is the value of the midpoint equal to the target? 10:30 Well, the value at that position is 7, so no. 10:34 In the else, we perform the first check. 10:37 Is the value at the midpoint less than the target? 10:40 Indeed it is. 10:43 So we call recursive binary search again and provide it a new list. 10:44 This list starts at midpoint plus one and goes to the end. 10:49 So in this case, that's a single-element list. 10:53 Since this is a new call to a recursive binary search, 10:56 we start back up at the top. 11:00 Is the list empty? 11:03 No, the midpoint is 0. 11:04 Is the value at the midpoint the same as the target? 11:05 It is, so now we can return True. 11:10 Remember a minute ago, I pointed out that when we call recursive_binary_search 11:12 from inside the function itself, it's preceded by a return statement. 11:17 That plays a pretty important role here. 11:21 So back to our visualization. 11:24 We start at the top, and we call binary search with a new list. 11:26 But because that's got a return statement before it, 11:30 what we're saying is, hey, when you run binary search on this, 11:33 whatever value you get back, return it to the function that called you. 11:37 Then at the second level we call binary search again, 11:41 along with another return statement. 11:44 Like with the first call, 11:46 we're instructing the function to return a value back to the code that called it. 11:48 At this level, we find the target so the function returns true back to the caller. 11:53 But since this inner function was also called by a function with instructions to 11:58 return, it keeps returning that true value back up until we 12:03 reach the very first function that called it. 12:06 Going back to our book of answers, recursive binary search instructs itself 12:09 to keep working on the problem until it has a concrete answer. 12:14 Once it does, it works its way backwards, giving the answer to every 12:18 function that called it until the original caller has an answer. 12:22 Now, like I said, at the beginning this is pretty complicated, so 12:26 you should not be concerned if this doesn't click. 12:30 Honestly, this is not one thing that you're gonna walk away with knowing fully 12:33 how to understand recursion after your first try. 12:37 I'm really not lying when I say I have a pretty hard time with recursion. 12:39 Now before we move on, I do want to point out one thing. 12:43 Even though the implementation of recursion is harder to understand, 12:46 it is easier in this case to understand how we arrive at the logarithmic run 12:51 time since we keep calling the function with smaller lists. 12:56 Let's take a break here. 13:00 In the next video, let's talk a bit more about recursion and why it matters 13:02
You need to sign up for Treehouse in order to download course files.Sign up