Computational thinking and problem-solving

Paper 4 · Unit 19. Searching, sorting, ADTs, Big O and recursion.

1. Searching

	Linear search	Binary search
Requirement	Works on any list	The list must be sorted
Method	Check each item in turn	Compare with the middle item and discard half each time
Worst case	n comparisons: O(n)	About log₂ n comparisons: O(log n)

Low ← 1
High ← N
Found ← FALSE
WHILE Found = FALSE AND Low <= High
   Mid ← (Low + High) DIV 2
   IF List[Mid] = Target THEN
      Found ← TRUE
   ELSE
      IF List[Mid] < Target THEN
         Low ← Mid + 1
      ELSE
         High ← Mid - 1
      ENDIF
   ENDIF
ENDWHILE

2. Sorting

Bubble sort repeatedly compares adjacent items and swaps them; a flag can stop early when no swaps occur. Insertion sort takes each item in turn and inserts it into the correct place in the already-sorted part. Both are O(n²) in the worst case; insertion sort is efficient for nearly sorted data.

FOR I ← 2 TO N
   Key ← List[I]
   J ← I - 1
   WHILE J > 0 AND List[J] > Key
      List[J + 1] ← List[J]
      J ← J - 1
   ENDWHILE
   List[J + 1] ← Key
NEXT I

3. Abstract data types

ADT	Key idea
Stack / queue / linked list	LIFO, FIFO and pointer-linked nodes (see Unit 10)
Binary tree	Each node has up to two children; in a binary search tree, left values are smaller and right values larger, giving fast search
Graph	Nodes connected by edges, possibly weighted or directed
Dictionary	Key–value pairs; look up a value by its key

ADTs can be implemented from built-in types such as arrays and records, or from each other (e.g. a queue from a linked list).

4. Big O notation

Big O describes how an algorithm’s time or space grows as the input size n grows, using the worst case.

Order	Name	Example
O(1)	Constant	Accessing an array element by index
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search
O(n²)	Polynomial (quadratic)	Bubble and insertion sort
O(2ⁿ)	Exponential	Some recursive algorithms

5. Recursion

A recursive subroutine calls itself. It needs a base case that stops the recursion and a general case that moves towards it. Each call is pushed onto the call stack with its parameters and return address; values are returned as the stack unwinds. Too many calls cause a stack overflow.

FUNCTION Factorial(N : INTEGER) RETURNS INTEGER
   IF N = 0 THEN
      RETURN 1                    // base case
   ELSE
      RETURN N * Factorial(N - 1) // general case
   ENDIF
ENDFUNCTION

6. Examiner tips

1. Binary search needs sorted data: always say so.
2. Trace recursion by showing each call and return value.
3. Big O: quote the worst case and explain what n is.
4. Insertion sort shifts items rather than swapping pairs.
5. Binary search tree: insert by comparing at each node, going left if smaller.

7. Practice questions

8. Topic test: predict your grade