>> [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]