ZAMYLA CHAN: Let's find the needle in the haystack.
Today in find.c we're going to help implement a program that
prompts the user for numbers to fill the haystack
and then searches the haystack for a needle.
Now, find.c calls sort and search, which are both functions
to find in helpers.c.
It's actually helpers.c where we're going
to be doing our programming today.
So what do we have to do?
Well, first we need to implement search, which
is a function that returns true if the value is found in the haystack
and false otherwise.
And then we also have to do sort, which sorts the values in the array
in incrementing order.
So first let's talk about search.
If you look at the distribution code in helpers.c
you'll find a preexisting linear search implementation
but we know that we can do much better than this.
Linear search is in O(n) time, which means that it's quite slow.
Instead of slowly iterating over every element of the list up until n,
let's talk about binary search.
Now, linear search can search any list, whereas binary search requires
that the list is sorted already.
But as long as you have a sorted list then binary search operates in O(log n)
time, which is quite efficient.
Let's take a look at an example.
Here I've populated an integer array of size nine with nine integers
and let's say we're looking for the number 17.
Now in this example, if we were to do a linear search
then it would take us 7 checks starting from index 0 all the way till index 7
to find that number.
So let's see how we can implement this using binary search
and find that needle a lot faster.
In binary search we start by looking at the whole array.
So from the left side of the array to the right side, we look at the entirety
and find the middle.
In this case, the middle is that index 4.
The value is 10.
So the assumption under binary search of the list is sorted.
So while 10 is not 17 and because the list is sorted,
we know that we don't need to look at the left half of the array anymore.
So similar to the way that we just throw aside
one half of the phone book in the beginning of this course,
we can just move our left bound all the way to the middle
but we've already checked the middle so we can get a little bit more efficient
and say, well since we've already checked the middle
we know that's not part of the array that we're looking for
so let's push they're bound to just beyond where the middle was.
So now we have our left bound at index 5 and our right bound stays the same.
Let's calculate the middle and we find, truncating the integer,
that the middle is at index 6.
So we check that value there, 16.
16 is not 17, in fact it's less than 17, which
means that we can discard the left half again and just look at the right side.
So then we move our left bound all the way to index 7 and the right bounds
stays at 8.
Calculating the middle between 7 and 8 brings us to 7.
We check that value and indeed we found our needle.
So let's talk about some pseudocode for this.
Essentially, while the length of the list
is greater than zero, that is we still have things to look at,
we want to look at the middle of the list
and if that middle is our needle if the number is found then that's great
and we can return true.
Otherwise we want to either search left or search right
depending on whether the number is higher or lower than our needle.
And then finally, if we've executed all of that
and we don't have any more list remaining then
that means that we return false because that
means that the needle is definitely not in that particular haystack.
Congratulations.
You've implemented a fast search, and now we can move on to sort.