ROB BOWDEN: Hi, I'm Rob. How do we employ a binary search? Let's find out. So, note that this search we're going to implement recursively. You could also implement binary search iteratively, so if you did that, that's perfectly fine. 

Now first, let's remember what the parameters to search are meant to be. Here, we see int value, which is supposed to be the value the user is searching for. We see the int values array, which is the array in which we're searching for value. And we see int n, which is the length of our array. 

Now, first thing first. We check to see if n equals 0, in which case we return false. That's just saying if we have an empty array, value is clearly not in an empty array, so we can return false. 

Now, we actually want to do the binary search part of binary search. So, we want to find the middle element of this array. Here, we say middle equals n divided by 2, since the middle element is going to be the length of our array divided by 2. Now we're going to check to see if the middle element equals the value we're searching for. So if values middle equals value, we can return true since we found the value in our array. 

But if that wasn't true, now we need to do the recursive step of binary search. We need to search either to the left of the array or to the middle of the array. So here, we say if values at middle is less than value, that means that value was greater than the middle of the array. So value must be to the right of the element that we just looked at. 

So here, we're going to search recursively. And we'll look at what we're passing to this in a second. But we're going to search to the right of the middle element. And in the other case, that means that value was less than the middle of the array, and so we're going to search to the left. Now, the left is going to be a bit easier to look at. So, we see here that we're recursively calling search where the first argument is, again, the value we're looking over. The second argument is going to be the array that we were searching over. And the last element now is middle. Remember the last parameter is our int n, so that's the length of our array. 

In the recursive call to search, we're now saying that the length of the array is middle. So, if our array was of size 20 and we searched at index 10, since middle is 20 divided by 2, that means we're passing 10 as the new length of our array. Remember that when you have an array of length 10, that means the valid elements are in indices 0 through 9. So this is exactly what we want to specify our updated array-- the left array from the middle element. 

So, looking to the right is a bit more difficult. Now first, let's consider the length of the array to the right of the middle element. So, if our array was of size n, then the new array will be of size n minus middle minus 1. So, let's think of n minus middle. 

Again, if the array were of size 20 and we divide by 2 to get the middle, so the middle is 10, then n minus middle is going to give us 10, so 10 elements to the right of middle. But we also have this minus 1, since we don't want to include the middle itself. So n minus middle minus 1 gives us the total number of elements to the right of the middle index in the array. 

Now here, remember that the middle parameter is the values array. So here, we're passing an updated values array. This values plus middle plus 1 is actually saying recursively call search, passing in a new array, where that new array starts in the middle plus one of our original values array. 

An alternate syntax for that, now that you've started to see pointers, is ampersand values middle plus 1. So, grab the address of the middle plus one element of values. 

Now, if you weren't comfortable modifying an array like that, you could also have implemented this using a recursive helper function, where that helper function takes more arguments. So instead of taking just the value, the array, and the size of the array, the helper function could take more arguments, including the lower index that you would care about in the array and the upper index that you care about the array. 

And so keeping track of both the lower index and the upper index, you don't need to ever modify the original values array. You can just continue to use the values array. But here, notice we don't need a helper function as long as we're willing to modify the original values array. We're willing to pass in an updated values. 

Now, we can't binary search over an array that is unsorted. So, let's get this sorted out. Now, notice that sort is past two parameters int values, which is the array that we're sorting, and int n, which is the length of the array that we're sorting. So, here we want to implement a sorting algorithm that is o of n squared. You could choose bubble sort, selection sort, or insertion sort, or some other sort we haven't seen in class. But here, we're going to use selection sort. 

So, we're going to iterate over the entire array. Well, here we see that we're iterating from 0 to n minus 1. Why not all the way up to n? Well, if we've already sorted the first n minus 1 elements, then the very last element what must already be in the correct place, so sorting over the entire array. 

Now, remember how selection sort works. We're going to go over the entire array looking for the minimum value in the array and stick that at the beginning. Then we're going to go over the entire array again looking for the second smallest element, and stick that in the second position in the array, and so on. So, that's what this is doing. 

Here, we're seeing that we're setting the current minimum value to the i-th index. So on the first iteration, we're going to consider the minimum value to be the start of our array. Then, we're going to iterate over the remainder of the array, checking to see if there any elements smaller than the one that we're currently considering the minimum. 

So here, values j plus one-- that's less than what we are currently considering the minimum. Then we're going to update what we think is the minimum to index j plus 1. So, do that across the entire array, and after this for loop, minimum should be the minimum element from the i-th position in the array. 

Once we have that, we can swap the minimum value into the i-th position in the array. So this is just a standard swap. We store in a temporary value-- the i-th value in the array-- put into the i-th value in the array the minimum value that belongs there, and then store back into where the current minimum value used to be the i-th value in the array, so that we didn't lose it. 

So, that continues on the next iteration. We'll start looking for the second minimum value and insert that into the second position. On the third iteration, we'll look for the third minimum value and insert that into the third position, and so on until we have a sorted array. My name is Rob, and this was selection sort.