Search Game One
Search Game Two
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
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.
- Very simple
- Can be using on sorted or unsorted lists
- Very slow
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.
- Very Fast, even with massive data sets
- 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.
Can you write the algorithm using a flowchart?
Activity 2 – Learning Log
Complete the learning log activities for this lesson.