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 3. 

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 phone book to the middle page in Week 0. 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 3, 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 your 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 pseudo code 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, one neat thing about this pseudo code 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.