Starter

  • Searching Game? how quick to find the letter using scratch
  • How quick to find the word using trinket
  • Board version – 20 questions
  • Higher or lower game?

Search Algorithms

What are search algorithms and why do we need them?
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.

search

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.
Advantages

  • Very Fast, even with massive data sets

Disadvantages
  • Can only be used with sorted lists

Binary vs Linear Search

Activity 1 – Card Sorting

Download and print a set of number cards ( You only need to print cards 1 to 20)

Cut out your cards and practice using a linear and binary search algorithm to search through for a number.

Activity 2 – Write your own algorithm

Using a language of your choice (e.g. Python or Scratch) write your own binary and linear search algorithms.

Activity 1 – Search practice

Activity 3 – Learning Log

Complete your learning log for today’s lesson.