AQA Computer Science GCSE
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:
REPEAT
name <- current name in the array
IF name = the one you're looking for THEN
IF found = True THEN
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:
FOR i <- 0 TO LEN(myArray)
IF name = the one you're looking for THEN
OUTPUT "found" + name
Using a FOR loop has some advantages and disadvantages.
Trace 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:
REPEAT
name <- middle name in the array
IF name = the one you're looking for THEN
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!)