That Blue Square Thing

AQA Computer Science GCSE

February 2019: this area of the site is being built just now. There are areas where there is no content yet. That will get added over the next 6 months or so.

Algorithms - Search Algorithms

You need to know about two sorts of search algorithm:

It's important to be able to compare the pros and cons of each of the two algorithms.

Linear Search

Start at the first item. Work your way through logically until you find the item you're looking for. Stop once you've found it.

Pretty basic, but it works.

Here's some pseudocode to implement a linear search:

found <- False
REPEAT
# start at the first name in the array
name <- current name in the array
IF name = the one you're looking for THEN
found <- True
ENDIF
UNTIL found = True OR reached end of list
IF found = True THEN
OUTPUT "found" + name
ELSE
OUTPUT "not found"
ENDIF

Note that this algorithm uses a REPEAT - UNTIL loop. This is a form of indefinite iteration. This means that the loop continues until the item required is found.

In Python REPEAT - UNTIL loops do not exist. You would need to use a WHILE loop instead. You need to realise that in pseudocode you may see REPEAT - UNTIL.

It would be possible to write the algorithm using a FOR loop as well, but this has some disadvantages. It would work like this:

found <- False
FOR i <- 0 TO LEN(myArray)
name <- the next item in the array
IF name = the one you're looking for THEN
found <- True
OUTPUT "found" + name
ENDIF
ENDFOR IF found = False THEN
OUTPUT "not found"
ENDIF

Using a FOR loop has some advantages and disadvantages.

PDF iconTrace table to use for search algorithms

Binary Search

A binary search will only work if the list can be sorted in some way, otherwise it's useless.

Start in the middle of the list - look at that item. Is it the one you want? If it is, stop.

If it isn't, you need to discard the half of the list the item can't be in - you can figure this out because the list is sorted. Then you find the middle of the remaining half and compare that with the one you're looking for - and repeat the process.

This sounds tricky, but working through some lists on the board will help make it easy to understand.

Here's an algorithm for a binary search:

found <- False
REPEAT
# start at the middle name in the array
name <- middle name in the array
IF name = the one you're looking for THEN
found <- True
ELSE
IF name > middle name in the array THEN
discard the first half of the array, including the middle name
ELSE
discard the second half of the array, including the middle name
ENDIF
ENDIF
UNTIL found = True or LEN(myArray) = 0 # the array is empty

A binary search can be really effective and computers use them all the time to find items quicker and more efficiently. But they don't apply to every situation and are rather more complex to code.

PDF iconTrace table to use for search algorithms (this is the same document as the one above!)

PDF iconBinary search exam question (with trace table).