Standard searching algorithms

Computer Science· Unit 9: Algorithm design & problem solving· 20 min read

1. Linear (Sequential) Search★★☆☆☆⏱ 6 min

📘 Definition

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
1. $8 \neq = 17$ , move to next element, index 1: value 3.
3
1. $3 \neq = 17$ , move to next element, index 2: value 17.
4
1. 17 matches the target. Return index 2 as the result.

2. Binary Search★★★☆☆⏱ 8 min

📘 Definition

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
1. First iteration: calculate midpoint = $\frac{0 + 6}{2} = 3$ . Value at mid is 15.
3
1. Compare $15 < 21$ : eliminate the left half, set low = mid + 1 = 4.
4
1. Second iteration: midpoint = $\frac{4 + 6}{2} = 5$ . Value at mid is 27.
5
1. Compare $27 > 21$ : eliminate the right half, set high = mid - 1 = 4.
6
1. Third iteration: midpoint = $\frac{4 + 4}{2} = 4$ . Value at mid is 21, which matches the target. Return index 4.

3. Complexity & Algorithm Selection★★★☆☆⏱ 6 min

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 (lo g n)$
Best case time complexity	$O (1)$	$O (1)$
Average case time complexity	$O (n)$	$O (lo g n)$
Space complexity (iterative)	$O (1)$	$O (1)$
Space complexity (recursive)	$O (n)$	$O (lo g 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
1. Binary search can only be used on sorted data, so it cannot be used without sorting first.
3
1. Sorting 1000 records adds unnecessary extra processing time.
4
Conclusion: Linear search is the appropriate choice for this scenario.

4. Common Pitfalls

Wrong move:

Using binary search on an unsorted dataset

Why:

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 move:

Use linear search for unsorted data, or sort the data first before applying binary search

Wrong move:

Off-by-one errors in binary search boundary calculations

Why:

Incorrectly setting low/high boundaries (e.g. setting low = mid instead of low = mid + 1) leads to infinite loops or missed targets

Correct move:

Always update boundaries to exclude the midpoint after comparison, since it has already been checked

Wrong move:

Claiming binary search always has a faster runtime than linear search

Why:

For small datasets, the overhead of boundary calculations in binary search can make it slower than a simple linear scan

Correct move:

State that binary search is asymptotically faster for large datasets, but may not be faster for small input sizes

Wrong move:

Stating linear search always has $O (1)$ space complexity

Why:

A recursive implementation of linear search uses $O (n)$ stack space for the call stack, not constant space

Correct move:

Specify if the implementation is iterative ( $O (1)$ ) or recursive ( $O (n)$ ) when asked for space complexity

5. Quick Reference Cheatsheet

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

When this came up on past exams

AI-estimated based on syllabus patterns — cross-check with official past papers for accuracy. Use only as revision-focus signals.

2022 · 12
Compare linear and binary search
2023 · 11
Write pseudocode for binary search
2024 · 13
State complexity of both searches

Going deeper

syllabusCIE 9618 Official SyllabusCheck for latest syllabus updates

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.