00:00:00,499 --> 00:00:04,290 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.