dcf.cymru stimulus sheet · Computer Science · Year 11
Search algorithm reference sheet
One sorted list, two correct algorithms and one broken one. The list is invented: 16 book ID numbers from one shelf of a school library, already sorted into ascending order.
The list
The list is called list and it is zero-indexed: the first item is list[0] and the last is list[15]. LENGTH(list) is 16.
| Index |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| Value |
4 | 9 | 15 | 21 | 26 | 33 | 38 | 42 |
47 | 55 | 61 | 68 | 72 | 80 | 86 | 93 |
Rules for tracing
- DIV is integer division: divide and throw away the remainder. 23 DIV 2 = 11, 15 DIV 2 = 7, 16 DIV 2 = 8.
- One comparison means one look at one item in the list. In binary search, lines 6 and 8 look at the same item, list[mid], so together they count as one comparison.
- RETURN ends the function immediately. A return value of −1 means "not found".
- Follow the lines exactly as written, even when you can see the answer. Tracing is about what the code does, not what it was meant to do.
Linear search
1 FUNCTION linearSearch(list, target)
2 FOR i ← 0 TO LENGTH(list) − 1
3 IF list[i] = target THEN
4 RETURN i
5 ENDIF
6 NEXT i
7 RETURN −1
8 ENDFUNCTION
Checks every item in turn from the front. It works on any list, sorted or not.
Binary search — Version A (correct)
1 FUNCTION binarySearch(list, target)
2 low ← 0
3 high ← LENGTH(list) − 1
4 WHILE low <= high
5 mid ← (low + high) DIV 2
6 IF list[mid] = target THEN
7 RETURN mid
8 ELSE IF list[mid] < target THEN
9 low ← mid + 1
10 ELSE
11 high ← mid − 1
12 ENDIF
13 ENDWHILE
14 RETURN −1
15 ENDFUNCTION
Looks at the middle item of the part of the list still in play, then throws away the half that cannot contain the target. It only works if the list is sorted.
Binary search — Version B (contains one logic error)
1 FUNCTION binarySearchB(list, target)
2 low ← 0
3 high ← LENGTH(list) − 1
4 WHILE low < high
5 mid ← (low + high) DIV 2
6 IF list[mid] = target THEN
7 RETURN mid
8 ELSE IF list[mid] < target THEN
9 low ← mid + 1
10 ELSE
11 high ← mid − 1
12 ENDIF
13 ENDWHILE
14 RETURN −1
15 ENDFUNCTION
Version B differs from Version A by one character. It still finds some items, which is exactly why this kind of error survives into real programs.
An unsorted list, for Step 6
| Index |
0 | 1 | 2 | 3 | 4 | 5 | 6 |
| Value |
30 | 12 | 55 | 7 | 41 | 19 | 60 |