Searching Algorithms Lesson Plan

Search Game One

Search Game Two

 

Game Discussion

Now that you have played the games, have a think about the following questions…

• Which of the two games was the easiest to find the right answer?
• Which of the two did you find it quickest to find the answer?
• Which of the two did it usually take less number of guesses to find the answer?

In the two games we had two different types of arrays(lists) – sorted lists and unsorted lists.

Search algorithms on computers

Often on your smart phone you might search for:

• a contact in order to call me
• a business or group on social media
• a location on a map

Computers store a massive amount of information, and it would be impractical (if not impossible) to look for all the data we need manually. This means that computers need to be able to search through information to find it. What method the computer uses is known as the search algorithm.

Linear vs binary search

When you search through the lists you might have just chosen cards at random but when a computer searches it will either use:

• Linear Search – for unsorted lists
• Binary search – for sorted lists

 

Linear Search

A linear search algorithm is an algorithm that starts at the beginning of a list and goes through each item in the list, looking for a match.

Advantages

• Very simple
• Can be using on sorted or unsorted lists

Disadvantages

• Very slow

 

Binary Search

A binary search algorithm is an algorithm that starts in the centre of a list and finds out of the value is greater or less than the value at the mid point (or if it is the value!)

The unused part of the list it then discarded and the process begins all over again. This type of algorithm is known as a divide and conquer algorithm. Divide and conquer algorithms are highly efficient, especially on large data sets. They are just used for searching as well – for example merge sort is a form of divide and conquer algorithm.

 

Advantages

• Very Fast, even with massive data sets

Disadvantages

• Can only be used with sorted lists

 

Activity 1 – Write your own search algorithms

Working on your own or with a friend write instructions to give another person for how to perform a linear search and a binary search algorithm.

 

Extension task

Can you write the algorithm using a flowchart?

Activity 2 – Learning Log

Complete the learning log activities for this lesson.