Last time, we learned what recursion is, and we saw how we can use recursion to calculate the factorial of a number. This time, we'll see how we can use recursion to do a binary search. For our second example, we'll revisit binary search, and I have a couple of helper functions that does a binary search on an even sized array, and the binary search on an odd sized array. This is the function we really care about. This is the recursive function. It's going to return an int. So it will return the location of the value we're searching for. If we don't find it, will return negative one because that's sort of standard protocol for saying, "I didn't find it". The function has four parameters: The value we are searching for. The array that we're searching for the value in. The lower bound, and the upper bound in the array that represents the portion of the array that we want to look in to try to find the search value. Let's go take a look at that function. We have two termination conditions for this problem. Either we've searched the entire array and we haven't found the search value, or we found the search value. Either one of those, stops our recursion because we're all done. How do we tell that we've searched the entire array? If we end up with a lower bound greater than upper bound, we have no range of values to look at for the search value, so we're all done. That means, we didn't find the value, so we've returned negative one. If we get past this point, we check the other termination condition. The way we do that is, first we take the range that we're looking at, upper bound minus lower bound, and divide by two. So that will help us get to the middle. But then we add it to lower bound because we may not be starting at zero rate. We may be looking between at five and nine, for example. So we'd want to look at seven. So upper bound minus lower bound in that example would be four, divided by two, is two. But we'd have to add that to five, the lower bound, to get to seven, which is the middle of the range that goes from five to nine. You don't have to worry about whether this rounds down or rounds up because it will work fine as long as we're consistent every time. Of course, we are consistent every time because it's the same line of code every time. Once we have the middle location, the location in the middle of our current search range, we look in the array at the element at that middle location and we say, that's our middle value. That's the element at the middle location. Now we check that other termination condition. To say, well, is that the search value? Because if it is, we found it, and we return middle location. The location of the middle value. However, we may not meet either of the two termination conditions, which means we need to keep looking. How do we keep looking? Because neither of our termination conditions were met. We now need to figure out which side of the range that we were searching this time we should keep searching in for the search value. Remember, binary search splits our search range in half each time. All we need to know at this point is, should we look at the lower half of the range we're looking at right now, or at the upper half? That's what this Boolean expression tells us. If middle value is greater than search value, that means that if search value is in fact in the array, it must be to the left of middle value. We pass in search value, we're still looking for the same number. We pass in search array. We're still looking in the same array for that number. Lower bound hasn't changed, but the upper bound is now middle location minus one. We know the value we're looking for isn't at middle location because if it were, that was one of the termination conditions. We know because middle value is greater than search value. If search value is actually in the array, we need to look to the left. So we keep lower-bound the same and push our upper bound to be just to the left of the middle of the range we're looking at here. If middle value isn't greater than search value, and remember we know it's not equal to search value because we would have then had a termination condition up above, then we need to look to the right of the middle location for our search value. Same value we are searching for, same array we're searching in. This time we bumped the lower bound to be just above the middle location and we leave upper bound the same. Let's set some break points and see how this actually works. I'm going to start by setting a break point here because I want to show as an example. The even sized array where the value is not in the array. So I'll run with F5 again, remember we're debugging and now that we've reached there. I'm going to set some breakpoints in the binary search function. I'll check for finding the first termination condition. I'll check for finding the second termination condition, and I'll stop here as well to see which side of the range we're going to look at next. I can F5. I did not hit either of those termination conditions. You can see down here that middle value is 17. Our search value is 43. I'll look at the locals. Our lower bound is zero and our upper bound is nine because the first time we call the binary search function, we're calling it with the entire array that we're searching in. But we know at this point we're looking for 43, the middle value is 17. So hopefully, we'll start looking to the right of where we're looking now. As you can see, I'm going to call the binary search function where we have moved the lower bound up. If I F5 again at this point, we're back in the binary search function again, as you can see on the right. This is the second time we've called the binary search function. You can also see over here that our lower bound is five and our upper bound is nine. So we are in fact searching the upper half of the array at this point. That middle value is 42, I actually put 42s all at the end of this array. So we still haven't found search value, and we're going to look to the right again because 43 is greater than 42. I've run it again. Now our lower bound is eight and our upper bound is nine. We're getting close, but we're not there yet. Our middle value is 42, and we're going to look to the right, again. I'll F5 to get to our break point. Our lower bound and our upper bound are the same, and that's not unusual because we need to check if that very last element in the array is the one we're looking for. It's not, it's 42 and we're looking for 43. So I'll F5 one more time. This time, lower bound is ten and upper bound is nine. Don't worry about all this junk because we hit this break point, where we had exhausted the search. So we haven't gotten to the point where we set middle location or middle value yet. So it's just whatever garbage is in memory. We haven't gotten there yet, and in fact, we never will on this particular call to binary search because we just hit one of the termination conditions. As you can see over here in the call stack, we have a number of recursive calls that we made to binary search until we finally reached the termination condition. I'll just make the code run to the end now. As you can see with the even array, the value is not in the array. That's the part we just step through. We didn't find the value, and that's the appropriate comment to provide when the binary search function returns negative one. To recap, in this lecture we learned how we can use recursion to do a binary search.
