So hopefully you liked my party celebration as much as I did. I am just as excited as you to be on our final section of see as awesome, as awesome as it is. It's been quite the long hall. I realized yesterday that I have been working on this for six months. Got a lot faster toward the end, but this is quite an accomplishment and you should feel incredibly accomplished to be practically at the end of this course. That said, unfortunately, the Recursive Binary Search and Merge Sort section really doesn't have the scaffolding needed, I think, for kids to understand it at all. They're not actually asked to do much of anything other than just run some code that's already there. I spent a long time to create some additional resources, but I also have a few more I'm hoping to have come in. I've actually hired some of my undergraduate students to create some bespoke, if you will, visualizers or animating. I'm hoping I'll be able to offer those to you later on. Watch for a reading after this video to include some of the most up-to-date recommendations of additional tools and resources you can use for teaching these topics. So starting off, they introduce recursive binary search. This paragraph is correct and it say, you know what? We've done this already. Remember, way back when we were in array list in unit 7, we're actually just using 1D arrays, but we did a linear search, which I grab this image from that video that we had then, and then we also had a binary search, where in the video, remember, it's like the telephone book or dictionary approach, where you look in the middle and then if it's still to the left of that, you throw all that away, if not to the left of that, you throw all that away and etc. Divide the problem in half every time. Maybe a better visual for your kids if you used this visualizer, which was the Liang visualizer. It's saying, "We are looking for the number eight and we already worked out and threw off the entire top half of the array because it was less than 10. So now we're just in the bottom half, we're currently looking at five, but we've only got these ones in gray left to do. So the idea being that we divide up the problem in half every time." Then, there's some code that does the exact same code that we did in unit 7 for iterative binary search, and they just told kids to want to say, here's a Java visualizer. To me, that doesn't help me visualize at all. The only goal of doing this is to get kids remembering what's binary search, how it works, to see the structure of it. We appointed you to this recommended visualizer before, which A, has the code on the left for the kids to map to, and B, is a more dynamic version of showing how we throw away parts of the array. They become grayed out, and then as we've got our low and our high value, etc. So I would do this one if you wanted them to remember what that was like. Again, the goal of having them and maybe walk through this is, when we see the structure of the problem we know that with recursion, we want to use it in a way that the structure of the problem can be easily seen to be recursive. So teacher tip for you, they're going to ask them kids next some questions to help them get at this. But the way that this fits into the recursive solution is, when we're starting off with the entire array, remember we look in the middle and we either find what we're looking for, and if we find it, we stop base case, or we decide we're going to do one half of the problem. We're going to do the left half or the right half, and that's the recursive case, and then we start essentially the same process over again. We take that, say the left half, check them at all, find it. If we got it, stop recursing or look inside, do we either recurse on the left-half of that part or the right half of that part. So it gets smaller by half every time, and we do the exact same two-part process. So this is what they have the kids asking us. What is the base case for recursive version? Again, that should be that you look at the middle point of the array that you have left, and if that is the answer you're looking for, then you're done. There's actually another one, but we'll get to that part later. It's when you don't find anything in there, there can be another check. Then this question is a little bit hard to parse, so let me break it up for you. The question is, write recursive method call that would search an array from zero to middle index? So they're not having to do binary search at all. We're just having to break the line of code that we call binary search. Up here, they actually give the method header, but because of a technical limitation of Runestone, they can't put it in that font that says, "This is text read." So it's just there in quotes, and that's going to be hard for kids to read, and also because it spans two lines. This is the method header, they are out there. I just think it's so much easier to read when it's in career and who format, etc. So let's review it. It has a return type of a Boolean, because it's a binary search, either you find it true or you don't find it false. We have an array that we're looking through. We have a target that we're looking for, a number, and we have a start index and an end index. So the answer to this question is binary search array, target, 0, array.length divided by 2. That's not the one that I'll point out. But if you're wanting to search the entire array, those last two values, 0 and array.length divided by 2, or this in the middle index. Yeah, it'll be the array. Note, this returns a boolean and I didn't catch it, anything. A better answer would be boolean found equal binary search array, target, 0, array.length divided by 2. Next, there's a big active code window with the recursive binary search. I'm going to walk you through it in parts. Let's start all the way at the bottom with main method. They have an array that we're looking for, and even though, boy, we should fix that. Even though they'd just talked about having binary search will return true or false, this recursive binary search for this is going to return an int. It's going to return the index where we found it. What are the parameters that we're passing to it? We're passing into it the array that we just declared, that we were searching for or searching in, where we are passing a number, that's the number we're searching for in that array, and then these two values are our start and end. When you are in a main method and you want to search an entire array, those two values are always going to be the same because you'll always want to say, I'm [inaudible] look over the whole array, which is 0 to array.length. I guess I can imagine some situation where you'd want to search only over part of it, but almost never. So those are pretty common. Always 0 and array.length. Now, let's go up to the recursive binary search again and check up there we got those four parameters, the array, the target, our start Index, and our end index. Were going to need those, we started off having this be the entire array, and again, as we go, we're going to be having those and moving start and end closer together as we look through just particular parts of the array. The first thing we do is we've got our start and our end, let's find the middle index for whatever part of the array we're currently looking for, and then do our base case. Let's look, is the thing that we're looking for target in the middle of this array? If so, we don't need to recurse. We found it and we return the index middle. Rather than true or false, we could do true. That'll be alright. But this one is doing return the index. So that's the base case, and that's where our recursion is going to stop. If you've found it, done. Well, here we go. Turns out there's another base case in this portion, which is, what if you don't? What if it's not in there, the target you're looking for is not in the array at all? You might remember back from our iterative binary search, we had things coming in and we check when they crossed over each other, and that's when our y loop stopped. Previously, I think we call them left and right, and when we said left was greater than right, we're using end and start. That might change when trying to decide if we can use common values or names for these, but start is on the left and end is on the right, and so if end is less than start, then we've crossed over and we're never going to find it because we've already looked through everything. In this case, since the target element is not in the array at all, we're going to return negative 1, which is that index value that indicates couldn't find it anywhere, because negative 1 is not a legal Index into our array. We've got two other options. These don't have to be if-else, if these could be an if-else would be better. But anyway, if the target, we're basically saying either recurse on the left half the array, if the target is less than the item at the middle, and we still pass in, we have to pass it in the array and the target we're looking for, the only thing we change are the start index and the end index, because we know we don't even need to look on the right half. So we keep the Start Index where it was, but we are in the check middle will do middle minus 1 and that's going to give us the left half. Then, if target is greater than array.middle, if it's bigger than that, then we're going to search end recurse on the right half of the array. Teacher tip, don't even bother talking about this with your kids. It's not that important. This is never actually going to happen because one of the other if is always going to be true, but Java can't be sure about that, and they say, "Hey, you're supposed to return an int. I need you to return an int." Return negative 1 is the right thing to do because that says, not found, but it's never going to happen. Again, I've looked and looked and looked for a really good simulator like this, where it steps through and visualizes it and shows you where you are in the recursive code. This is the iterative code, we did back in unit 7. Check back later. I have assigned some students to create one. I don't know if there'll be successful, but I'm hoping I'll be able to get you something.
