[MUSIC] In this part of the course, we're looking at some common algorithms. The first one we looked at was finding the largest value in a collection. Now we'll look at another common algorithm which is determining whether a collection contains a given value. Recall from the LGBT Center case study, that we were scheduling times for them to meet with different student groups. And one thing we may want to know is whether they have already scheduled a meeting at a given time. So the LGBT Center may have a list of all the meeting times they have already scheduled, and they want to see whether that list contains a particular time. We'll call this searching for a value. If so, then they'll know that they can't schedule a meeting at that time. Let's say that the times shown here are when meetings are already scheduled. And you want to know if there's a meeting scheduled for Wednesday at 2 PM. Looking at the list, you can see that Wednesday at 2 PM is already there. So they cannot schedule another meeting at that time. So how did you determine if a meeting was already scheduled at a particular time? Well, it's very similar to the example of looking for the largest value in a collection. Your eyes have gotten pretty good at looking at lots of pieces of data and making quick subconscious decisions about them. And you've probably had a lot of experience comparing words and numbers and recognizing them quickly by their shape. You didn't care that the times were not ordered, i.e., that Friday at 3 PM comes before Monday at 10 AM. But as we saw last time, a computer can't process that information all at once. In other words, it can't just look at all eight dates and determine whether it sees the one it's looking for. It can only inspect each date one at a time and perform a comparison. So how can we write an algorithm using just binary comparisons? Well, it's pretty similar to what we saw last time. Let's say that we're looking for Wednesday at 2 PM, which we will call the target. We start by indicating that we have not yet found the value. We haven't even started. We then look at each date, one by one, and compare with the target. If it's the same, then we found it. Note that we can stop as soon as we find the target. On the other hand, if we're looking for Thursday at 2 PM, then we must look at all of the dates to determine that the slot has not already been taken. Again, we start with found being no. We then look at each value in the list and come all the way to the end, without finding the target. So it's not found and we can output NO. This is called a linear search because we look at all the values once. Now that we've worked through these examples, let's see how we would express the algorithm in English. It's pretty similar to the algorithm we saw last time with a few important changes. The problem is to determine whether a list contains a target value. To do this, we look at each value in the list and compare against the target. If it is equal to the target then we have found the value and we can stop looking. If we go through the entire list and have not found the target, then it is not in the list. We can also write the flowchart for this. We start by getting input about the list and target value. If there is an untested item in the list, which initially there is, if the list is not empty, then we get an item and compare against the target. If it is equal to the target then we have found the target and output true. Otherwise, we repeat the process. When there are no more untested items, we've looked at the entire list and have not found it. We therefore output false. So now we understand how to find a value in the list, like finding if a particular meeting time for the LGBT center has already been taken. This follows a similar pattern to finding the maximum value in a list. In the case of searching for value, sometimes we needed to look through the entire list, i.e., when the meeting time has not been taken. However, if the meeting time was taken, we could stop as soon as we found a time slot in the list. This could be as soon as the first element in the list or the sixth, as was the case for seeing if Wednesday at 2 PM was available. The algorithm certainly works but the question is, can we do better? Note that if the list was very long, this could take a very long time. We will return to this soon. Stay tuned.