# Standard searching algorithms

> Computer Science · CIE A-Level 9618
> Source: https://www.owlsprep.com/study/cie-9618-u9-standard-searching-algorithms/

This module covers the two standard searching algorithms for CIE A-Level 9618: linear (sequential) search and binary search. You will learn how they work, their complexity, and when to use each in exam problems.

**Prerequisites:** [Basic algorithm pseudocode conventions](https://www.owlsprep.com/study/cie-9618-u8-pseudocode-conventions/); [Big O notation for algorithm complexity](https://www.owlsprep.com/study/cie-9618-u9-time-space-complexity/)

## Learning objectives

- Distinguish between linear and binary search algorithms
- Implement linear and binary search correctly for sorted and unsorted data
- Compare the time and space complexity of standard searching algorithms
- Identify which search algorithm is appropriate for a given exam problem scenario

## Linear (Sequential) Search

**Linear Search** — A brute-force sequential search algorithm that iterates through every element in a dataset in order, comparing each element to the target value until a match is found, or the end of the dataset is reached. Works on both sorted and unsorted datasets.

*Example:* Finding a specific name in an unsorted list of student IDs.

Linear search is the simplest searching algorithm, requiring no pre-processing of the input dataset. It can be implemented on any sequential data structure, including arrays, linked lists, and unsorted linear collections.

**Worked example:** Find the target value 17 in the array `[8, 3, 17, 5, 12]` using linear search. Step through the algorithm.

1. 1. Start at the first element, index 0: value 8. Compare to target 17.
2. 2. $8 \neq 17$, move to next element, index 1: value 3.
3. 3. $3 \neq 17$, move to next element, index 2: value 17.
4. 4. 17 matches the target. Return index 2 as the result.

> **tip**
>
> Always remember that linear search works on unsorted data. If your data is not sorted, linear search is the only standard option you can use without pre-processing.

## Binary Search

**Binary Search** — A divide-and-conquer search algorithm that repeatedly divides the sorted search space in half, reducing the number of elements to check by 50% each iteration. Only works on pre-sorted datasets.

*Example:* Finding a specific word in a sorted printed dictionary.

Binary search relies on the sorted property of the input to eliminate half the search space after each comparison. It can be implemented either iteratively or recursively.

**Worked example:** Find the target 21 in the sorted array `[3, 7, 12, 15, 21, 27, 32]` using binary search. Step through the process.

1. 1. Initialise low = 0 (start index), high = 6 (end index of the array)
2. 2. First iteration: calculate midpoint = $\frac{0 + 6}{2} = 3$. Value at mid is 15.
3. 3. Compare $15 < 21$: eliminate the left half, set low = mid + 1 = 4.
4. 4. Second iteration: midpoint = $\frac{4 + 6}{2} = 5$. Value at mid is 27.
5. 5. Compare $27 > 21$: eliminate the right half, set high = mid - 1 = 4.
6. 6. Third iteration: midpoint = $\frac{4 + 4}{2} = 4$. Value at mid is 21, which matches the target. Return index 4.

> **warning**
>
> Binary search only works on sorted datasets. If the dataset is unsorted, you must sort it first, which adds $O(n \log n)$ time to the overall process.

## Complexity & Algorithm Selection

In CIE exams, you will often be asked to compare the two algorithms, state their time and space complexity, and select the appropriate algorithm for a given scenario.

| Property | Linear Search | Binary Search |
| --- | --- | --- |
| Works on unsorted data | Yes | No |
| Requires pre-sorting | No | Yes |
| Worst case time complexity | $O(n)$ | $O(\log n)$ |
| Best case time complexity | $O(1)$ | $O(1)$ |
| Average case time complexity | $O(n)$ | $O(\log n)$ |
| Space complexity (iterative) | $O(1)$ | $O(1)$ |
| Space complexity (recursive) | $O(n)$ | $O(\log n)$ |

**Worked example:** A school stores 1000 unsorted student records. Which search algorithm should be used to find a student's record by ID? Justify your answer.

1. 1. Confirm the dataset property: the question explicitly states records are unsorted.
2. 2. Binary search can only be used on sorted data, so it cannot be used without sorting first.
3. 3. Sorting 1000 records adds unnecessary extra processing time.
4. Conclusion: Linear search is the appropriate choice for this scenario.

**Exam command terms**

Common exam command terms for this topic have specific expectations:

- **Distinguish** — State key differences between the two algorithms, usually comparing properties like complexity and use case *(Distinguish between linear and binary search)*

- **Write pseudocode** — Write a working algorithm using CIE standard pseudocode conventions, including all loops and conditional checks *(Write pseudocode for an iterative binary search)*

## Common pitfalls

- **Wrong:** Using binary search on an unsorted dataset
  - Why it fails: Binary search relies on sorted order to eliminate half the search space, it will often fail to find an existing target in unsorted data
  - Correct: Use linear search for unsorted data, or sort the data first before applying binary search
- **Wrong:** Off-by-one errors in binary search boundary calculations
  - Why it fails: Incorrectly setting low/high boundaries (e.g. setting low = mid instead of low = mid + 1) leads to infinite loops or missed targets
  - Correct: Always update boundaries to exclude the midpoint after comparison, since it has already been checked
- **Wrong:** Claiming binary search always has a faster runtime than linear search
  - Why it fails: For small datasets, the overhead of boundary calculations in binary search can make it slower than a simple linear scan
  - Correct: State that binary search is asymptotically faster for large datasets, but may not be faster for small input sizes
- **Wrong:** Stating linear search always has $O(1)$ space complexity
  - Why it fails: A recursive implementation of linear search uses $O(n)$ stack space for the call stack, not constant space
  - Correct: Specify if the implementation is iterative ($O(1)$) or recursive ($O(n)$) when asked for space complexity

## Cheatsheet

| Algorithm | Pre-requisite | Worst Time | Best Use Case |
| --- | --- | --- | --- |
| Linear Search | None | $O(n)$ | Small/unsorted datasets |
| Iterative Binary Search | Sorted data | $O(\log n)$ | Large sorted datasets |
| Recursive Binary Search | Sorted data | $O(\log n)$ | Recursive problem solutions |

## What's next

Standard searching algorithms are a foundational building block for more complex algorithmic problems you will encounter in the rest of the unit. Searching is a core component of many higher-level algorithms, including sorting algorithms, graph traversal, and database query processing. Mastering the difference between linear and binary search will help you correctly answer problem-solving questions in both paper 1 and paper 2 of your exam, and you will often be asked to write pseudocode or trace through these algorithms directly. Next, you can learn about standard sorting algorithms, which are often paired with searching in exam questions.

- [Standard Sorting Algorithms](https://www.owlsprep.com/study/cie-9618-u9-standard-sorting-algorithms/)
- [Algorithm tracing](https://www.owlsprep.com/study/cie-9618-u9-algorithm-tracing/)
- [Data types & structures](https://www.owlsprep.com/study/cie-9618-u10-overview/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/cie-9618-u9-standard-searching-algorithms/