In this lecture, we'll look at another problem that we can use recursion to solve. Specifically, we'll see how we can do binary search using recursion. We will again use Visual Studio so we can use the debugger to look at how recursive binary search works. So we'll walk through one of these, where we have an array. Of one, three, five, 12, 17, 21, 33, 42, 42 and 42. And we are going to do a binary search of this array. So we are going to pass in the number we're looking for, which is three. We're going to pass in the array we're going to search, we'll pass in the lower bound and will pass in the upper bound. So we start with a lower bound of zero and an upper bound of the array length minus one. We start by saying, we need to search the entire array. Let's go look at the binary search method to see how it works. So as I said, we pass in a search value in the array, and a lower bound and an upper bound. And we are going to recurse until one of two things happen. So we have two base cases in this particular case. One of those base cases is that there is nothing else to look at, and that is the case when lower bound is greater than upper bound, then there is nothing else for us to look at. So we return negative one because we didn't find the value we were looking for in the array. We also might have found the search value when we look at the middle location, and so if we've found the value, we return it's location. And here's where the recursion comes in. If in fact, the middle value is greater than search value, then we know that the value we're looking for is on the left. So we make a recursive call to the method. We're still looking for search value, and we're still looking for it in the search array. We leave the lower bound the same, but we set the upper bound to middle location minus one. So now we're looking at a chunk of the array to the left of middle location. Similarly, if the middle value is less than search value, then we are going to search for the value in the array. But this time we're going to look to the right of middle location. So our lower bound gets moved up to middle location plus one, and our upper bounds stays the same. So let's use the debugger to watch what happens. I'll set a break point here in the binary search method, and we will start debugging with F5. So we are looking for the value three, the call stack shows our first call on the binary search method, our lower bound is zero and our upper bound is nine because we have 10 elements in the array. I will have F10 a few times so we're calculating the middle location, and down here on the left you can see that the middle location is four at this point. And we F10 one more time, and middle value is 17. So we know 17 is greater than the three we're looking for, we are going to keep searching. I'll F5, so you can see over here in the call stack or in our recursive call on the binary search method, at this point lower bound is zero and upper bound is three. I'll F10 and I'll F10 one more time, and a middle location is one and middle value is three. So we've actually just found with one recursive call, two calls to the binary search method, but when recursive call to the binary search method where we changed upper bound, so we were shrinking the conceptual size of the array that we were searching for the element each time we called the method. And so this is our first base case, I'll F10 to show you that we in fact, are going to return middle location because we found three which is what we're looking for. I'm going to F5 again, and I will tell you that this time we are searching for the value 43 which is not in the array. We start with our lower bound of zero and our upper bound of nine. And I will F5 and you'll see in the call stack this is our first recursive call. And because 43 was greater than 17, we are now going to change our lower bound to five and our upper bound to nine. Let's see what that middle value we're comparing to is. It's 42, and 43 is greater than 42 so I'm going to F5 again. Here you can see in the call stack we're now in our second recursive call to binary search. Lower bound is eight, upper bound is nine.. We're going to find 42 again, so I'll F5 again. Here you can see lower bound and upper bound are both nine, and we're in our third recursive call to the binary search method. I'll F5 one more time. There's our last recursive call, lower bound is 10, and upper bound is nine. So I will F10 to show you that we're returning negative one here because we hit the other base case for the recursion, where there was nothing else to look at, and we didn't find the value we were looking for in the array. To recap. In this lecture, we saw how we can do a binary search using recursion.