Searching Algorithms

Use this interactive page to investigate the difference between linear and binary searching algorithms and see which is the most efficient for different numbers. This is suitable for KS3 Computing and is a requirement for GCSE Computer Science.

What is Searching?

In Computing, the word search means finding a particular value in a list of sorted values. It is a technique similar to searching for an answer using the trial and improvement method of solving an equation for GCSE Maths.

Searching and sorting should really be considered together. These search algorithms only work on sorted data, and time spent sorting your data will save time when searching. This how much easier it is to find a book or a CD on your shelf if they are in order - and how finding a book in a library would be nearly impossible if the books weren't sorted.

Investigate

The KS3 National Curriculum for Computing says that students need to be aware of different types of algorithms. This page compares the two most common searching algorithms - the linear search and the binary search - to find the whole number that you are thinking of.

Search

Type of search :

Maximum value:

Think of a whole number between 1 and your maximum value and click the Go! button.

Guesses

Questions

Which of these searches found your number more quickly?
Does the number you choose make a difference? Could you choose a number that would make the linear search faster than the binary search?
On average, how many guesses would the linear search make? What is the maximum number of guesses that the binary search needs?

If you're preparing for GCSE Computer Science then you might like to look at a version of the binary sort algorithm coded in Python - it gives a commentary in the style of an exam answer. Try changing the program so that it finds a number from 1-1000 - how many guesses does the binary search need then?

There is also a similar page that allows you to compare sorting algorithms.