19.1 Algorithms

2026 Syllabus Objectives

By the end of this topic, you should be able to:

  • understand linear search and binary search

  • write an algorithm for a linear search

  • write an algorithm for a binary search

  • explain the conditions needed for binary search to work

  • explain how the performance of binary search changes as the number of data items changes

  • understand insertion sort and bubble sort

  • write an algorithm for insertion sort

  • write an algorithm for bubble sort

  • explain how sorting performance depends on:

    • the number of data items
    • the initial order of the data

  • understand and use Abstract Data Types (ADTs)

  • write algorithms to find an item in:

    • a linked list
    • a binary tree

  • write algorithms to insert an item into:

    • a stack
    • a queue
    • a linked list
    • a binary tree

  • write algorithms to delete an item from:

    • a stack
    • a queue
    • a linked list

  • understand that a graph is an example of an ADT

  • describe the key features of a graph

  • justify why a graph is useful in a given situation

  • explain how one ADT can be implemented using another ADT or built-in type

  • describe how these ADTs can be implemented:

    • stack
    • queue
    • linked list
    • dictionary
    • binary tree

  • compare algorithms using:

    • time taken
    • memory used

  • use Big O notation for time complexity and space complexity

Main Content

https://cambridgeassistant.com

Linear Search

A linear search is the simplest way to find an item in a list. You start at the first item and check each item one by one until:

  • the item is found, or
  • the end of the list is reached

This search does not need the list to be sorted. That is why it is useful when data is in any order.

Imagine a list:

[12, 7, 25, 9, 18]

If you want to find 9, a linear search checks:

  • 12 → not a match
  • 7 → not a match
  • 25 → not a match
  • 9 → match found

So the search stops as soon as it finds the value.

A linear search is easy to write and easy to understand. Its weakness is that it can be slow for large lists, because in the worst case it may need to check every single item.

Linear search algorithm

FUNCTION LinearSearch(List, Item) RETURNS INTEGER
    DECLARE Index : INTEGER
    DECLARE Found : BOOLEAN

    Index ← 0
    Found ← FALSE

    WHILE Index < LENGTH(List) AND Found = FALSE
        IF List[Index] = Item THEN
            Found ← TRUE
        ELSE
            Index ← Index + 1
        ENDIF
    ENDWHILE

    IF Found = TRUE THEN
        RETURN Index
    ELSE
        RETURN -1
    ENDIF
ENDFUNCTION

This algorithm returns the index of the item if it is found. It returns -1 if the item is not in the list.

Performance of linear search

If the list has n items:

  • best case: the item is first, so the search is very quick → O(1)
  • worst case: the item is last, or not present, so every item is checked → O(n)
  • average case: about half the list is checked → still described as O(n)

For memory use, linear search only needs a few extra variables such as a counter and a flag. So the extra memory is very small and is usually treated as O(1).

Binary Search

A binary search is a faster search method than linear search, but it only works under the right conditions.

Binary search works by repeatedly checking the middle item of the current search area.

There are three possible cases:

  1. the middle item is the value you want
  2. the value you want is smaller than the middle item, so search the left half
  3. the value you want is larger than the middle item, so search the right half

Each time, half of the remaining list is ignored.

Important condition for binary search

The list must be sorted before binary search can be used.

If the data is not sorted, binary search can give the wrong answer because the decision to go left or right depends on the values being in order.

For example, in this sorted list:

[16, 19, 21, 27, 36, 42, 55, 67, 76, 89]

If you search for 19:

  • middle item might be 36
  • 19 < 36, so search left half
  • next middle might be 19
  • found

This is much faster than checking every value from the start.

Midpoint calculation

The middle position is found using:

[ \text{mid} = \left\lfloor \frac{\text{lowerBound} + \text{upperBound}}{2} \right\rfloor ]

This means add the two bounds and divide by 2, rounding down to an integer.

Binary search algorithm

FUNCTION BinarySearch(List, Item) RETURNS INTEGER
    DECLARE LowerBound : INTEGER
    DECLARE UpperBound : INTEGER
    DECLARE Mid : INTEGER
    DECLARE Found : BOOLEAN

    LowerBound ← 0
    UpperBound ← LENGTH(List) - 1
    Found ← FALSE

    WHILE LowerBound <= UpperBound AND Found = FALSE
        Mid ← (LowerBound + UpperBound) DIV 2

        IF List[Mid] = Item THEN
            Found ← TRUE
        ELSE
            IF List[Mid] < Item THEN
                LowerBound ← Mid + 1
            ELSE
                UpperBound ← Mid - 1
            ENDIF
        ENDIF
    ENDWHILE

    IF Found = TRUE THEN
        RETURN Mid
    ELSE
        RETURN -1
    ENDIF
ENDFUNCTION

How the performance of binary search changes with the number of items

Binary search is efficient because it cuts the list in half each time.

If the number of items increases, the number of comparisons increases very slowly.

For example:

  • with 8 items, about 3 comparisons may be enough
  • with 16 items, about 4 comparisons
  • with 1024 items, only about 10 or so steps are needed in theory, and still far fewer than a linear search

This is why binary search has O(log n) time complexity.

That means:

  • when the list becomes much bigger, the number of steps grows slowly
  • doubling the size of the list does not double the number of steps

Binary search compared with linear search

A binary search is usually much faster than a linear search on a large sorted list.

A linear search may still be better when:

  • the list is very small
  • the item is near the start of the list
  • the list is not sorted

So binary search is not always the best choice. The algorithm must match the data.

Sign in to view full notes