Lesson 5.2: Linear Searching

Learning Objectives:
With the invention of the internet came a massive influx of data and information. Now that we have such an abundance of information, the problem of searching arises. How do we find what we are looking for when there is so much information out there? In this unit we explore searching algorithms and how these algorithms help us find what we are looking for.
  • Students will learn how companies such as google use searching algorithms
  • Students will discuss how they use searching in their everyday lives
  • Students will learn what the linear searching algorithm is and when to use it

Do Now: 
Watch: 

YouTube Video


Read:
In the world today there is a nearly endless supply of information, or data, available. However, all this information does not help us very much if we cannot search through all of it and find exactly what we want. In this section we will talk about some search algorithms that we often use to find things in our everyday lives. However, searching isn't just an important skill to have when we need to find our favorite red shirt or where the yogurt is located in the super market. It is also extremely important to be able to search efficiently on the internet. Companies such as Google have made our lives easier by creating search engines. These search engines use very complex searching algorithms to find information. Even though the searching algorithms we use in our day to day lives are much less complex than the search algorithms Google uses, the same purpose underlies both types of searches. We want to be able to find exactly what we are looking for in the shortest amount of time possible. Watch the video below to see how Google constantly improves its famous search algorithm!



Explore: 
Activity: Watch and Discuss

YouTube Video

VIDEO DISCUSSION

As you can see, Google puts a lot of time and effort into improving its search algorithm. In fact, developing efficient searching techniques is an important part of computer science. 

However, the internet is not the only place where it is necessary to search through a lot of data to find what you want. Can you think of other senarios in which it is important to be able to efficiently search for something?


Activity Part 2: Introduction to Linear Searching

Often times in computer science it can be beneficial to find the maximum, the minimum, or any specific value in a list. In this activity you will try to figure out the most efficient method of searching for a specific element in an unordered list of elements.

Split into pairs and pick one person to be the chef and one person to be the artist. The artist cuts up the color cards and the chef cuts up the food cards. The artist should mix up the color cards and arrange them in a line face down. The chef should try to find the "red" card, but he/she can only flip over one card at a time. After the chef finds the card, he/she should shuffle the food cards and place them face down on the table. Now, the artist should try to find the "pizza" card keeping in mind that he/she can only flip over one card at a time. Click on the link above or the picture below to get started! Good luck!

Encoding and Decoding Messages Worksheet

Activity Discussion

  • How many cards did you have to flip over before finding the card you were looking for?
  • How many cards did your partner have to flip over before finding the card he/she was looking for?
  • What method did you use in order to find your card quickly?
  • How many cards would you have had to flip over if you were asked to find a card that was not included in the set of color or food cards?
  • If you had 100 cards what is the maximum number of cards you would have to overturn using your method?
  • If you had x number of cards what is the maximum number of cards you would have to overturn using your method?

Activity Part 3: Linear Searching

One common method that you could have used in the activity above is the linear search algorithm. This algorithm is often applied when you have a list of unordered elements (these elements can be numbers, colors, foods, or anything else you can think of) and want to find a specific element in this list. Linear searching finds the target element by looking at the first element in the list and comparing it to the element it wants to find (the target element). If the first element is the target element the linear search is done! Otherwise, the next element in the list is compared to the target element. This process continues until the target element is found or the list of elements ends. 

What the video below to see for yourself how linear searching works.

YouTube Video



Lesson 5.2 Wrap Up:
Reflection: 
  • What made finding the card difficult or frustrating?
  • How might you arrange the cards differently to help you find your card faster? Hint: Could you find the card faster in a list that was arranged from lowest to highest?
  • If you don't know the answer to the last question do not worry! We will cover this in more detail in the next section.
  •                      
Comments