[MUSIC PLAYING] 

ZAMYLA CHAN: The first thing you might notice about find is that we already have code written for us. This is called distribution code. So we're not just writing our own code from scratch anymore. Rather, we're filling in the voids in some pre-existing code. 

The find.c program prompts for numbers to fill the haystack, searches the haystack for a user submitted needle, and it does this by calling sort and search, functions defined in helpers.c. So find.c is written already. Your job is to write helpers. 

So what are we doing? We're implementing two functions. Search, which returns true if a value is found in the haystack, returning false if the value is not in the haystack. And then we're also implementing sort which sorts the array called values. 

So let's tackle search. Search is currently implemented as a linear search, but you can do much better than that. Linear search is implemented in O of n time, which is quite slow. Although, it can search any list given to it. Your job is to implement binary search, which has run time O of log n. That's pretty fast. 

But there's a stipulation. Binary search can only search through pre-sorted lists. Why is that? 

Well let's look at an example. Given an array of values, the haystack, we're going to be looking for a needle. And in this example, the integer three. The way that binary search works is that we compare the middle value of the array to the needle, much like how we opened a phonebook to the middle page in week zero. 

So after comparing the middle value to the needle, you can discard either the left or the right half of the array by tightening your bounds. In this case, since three, our needle, is less than 10, the middle value, the right bound can decrease. But try to make your bounds as tight as possible. If the middle value isn't the needle, then you know that you don't need to include it in your search. So you're right bound can tighten the search bounds just a tiny bit more, and so on and so forth until you find your needle. 

So what does the pseudocode look like? Well while we're still looking through the list and still have elements to look in, we take the middle of the list, and compare that middle value to our needle. If they're equal, then that means we've found the needle and we can return true. 

Otherwise, if the needle is less than the middle value, then that means we can discard the right half, and just search the left side of the array. Otherwise, we'll search the right side of the array. And at the end, if you don't have any more elements left to search but you haven't found your needle yet, then you return false because the needle definitely isn't in the haystack. 

Now a neat thing about this pseudocode in binary search is that it can be interpreted as either an iterative or recursive implementation. So it would be recursive if you called the search function within the search function on either half of the array. We'll cover recursion a bit later in the course, but do know that it is an option if you'd like to try. 

Now let's look at sort. Sort takes an array and the integer n, which is the size of the array. Now there are various different types of sorts, and you can look at some shorts for demos and explanations. The return type for our sort function is void. So that means that we're not going to return any array from sort. We're actually going to change the very array that was passed into us. 

And that's possible because arrays are passed by reference in C. Now we'll see more about this later, but the essential difference between passing in something like an integer and passing in an array, is that when you pass in an integer, C is just going to make a copy of that integer and pass it to the function. The original variable won't be changed once the function is finished. With an array, on the other hand, it's not going to make a copy, and you'll actually be editing the very array itself. 

So one type of sort is the selection sort. The selection sort works by starting at the beginning, and then you iterate over and find the smallest element. And then you swap that smallest element with the first one. And then you move to the second element , find the next smallest element, and then swap that with the second element in the array because the first element is already sorted. And so then you continue for every element in identifying the smallest value and swapping it out. 

For I equals 0, the very first element to n minus 1, you're going to compare every next value after that and find the index of the minimum value. Once you find the minimum value index, you can swap that value of array minimum and array I. 

Another type of sort that you can implement is bubble sort. So bubble sort iterates over the list comparing adjacent elements and swapping the elements that are in the wrong order. And this way, the largest element will bubble to the end. And the list is sorted once no more elements have been swapped. 

So those are two examples of sort algorithms that you can implement for the find program. Once you finish sort, and you've done search, you're finished. My name is Zamyla, and this is CS50. 

[MUSIC PLAYING]