# That Blue Square Thing

## AQA Computer Science GCSE

September 2020: This page is the for the 2022 exam version of the AQA Computer Science GCSE course. This is for Year 10 teaching in September 2020.
These pages were copied over from the old syllabus and will get updated as I work through the new one. That means they won't always be totally up to date and I might miss something - check the updated date at the bottom of the page.

### Algorithms - Search Algorithms

You need to know about two sorts of search algorithm:

• linear search
• binary search

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
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
ENDIF

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

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