Searching Algorithms: Linear and Binary Search

Searching algorithms are used to find a specific item within a data set. In GCSE Computer Science, you must understand two key searching algorithms: linear search and binary search. You need to know how each one works, be able to trace through them, and compare their efficiency.

---

Linear Search

A linear search (also called a sequential search) works by checking each item in the list one at a time, starting from the first item and moving through to the last. It continues until the item is found or the end of the list is reached.

How Linear Search Works

1. Start at the first item in the list
2. Compare the current item with the item you are searching for
3. If it matches, the search is complete — return the position
4. If it does not match, move to the next item
5. Repeat steps 2-4 until the item is found or the end of the list is reached
6. If the end of the list is reached without finding the item, the item is not in the list

Pseudocode for Linear Search

FUNCTION linearSearch(list, target)
    FOR i ← 0 TO LENGTH(list) - 1
        IF list[i] = target THEN
            RETURN i
        END IF
    END FOR
    RETURN -1     // Item not found
END FUNCTION

Trace Example

List: [4, 7, 2, 9, 1, 5] Target: 9

Step	i	list[i]	list[i] = target?	Action
1	0	4	NO	Continue
2	1	7	NO	Continue
3	2	2	NO	Continue
4	3	9	YES	Return 3

Result: Found at index 3

Key Properties of Linear Search

• Does not require the list to be sorted — works on any list
• Simple to implement — very straightforward code
• Slow for large lists — in the worst case, every item must be checked
• Best case: 1 comparison (item is at the start)
• Worst case: n comparisons (item is at the end or not in the list)
• Average case: n/2 comparisons

Exam Tip: Linear search is the only option if the data is unsorted. If asked when you would use a linear search, mention that the data does not need to be in any particular order.

---

Binary Search

A binary search works by repeatedly dividing the search space in half. It starts by checking the middle item of a sorted list. If the target is smaller, it searches the left half; if larger, it searches the right half. This process repeats until the item is found or the search space is empty.

Prerequisites

Binary search only works on sorted data. If the data is not sorted, you must sort it first (which takes time) or use a linear search instead.

How Binary Search Works

1. Set the low pointer to the start of the list and the high pointer to the end
2. Find the middle item: middle = (low + high) DIV 2
3. Compare the middle item with the target:
   • If it matches, the search is complete — return the position
   • If the target is less than the middle item, set high = middle - 1 (search left half)
   • If the target is greater than the middle item, set low = middle + 1 (search right half)
4. Repeat steps 2-3 until the item is found or low > high
5. If low > high, the item is not in the list

Pseudocode for Binary Search

FUNCTION binarySearch(list, target)
    low ← 0
    high ← LENGTH(list) - 1
    WHILE low <= high
        mid ← (low + high) DIV 2
        IF list[mid] = target THEN
            RETURN mid
        ELSE IF target < list[mid] THEN
            high ← mid - 1
        ELSE
            low ← mid + 1
        END IF
    END WHILE
    RETURN -1     // Item not found
END FUNCTION

Trace Example

Sorted list: [1, 3, 5, 7, 9, 11, 13, 15] Target: 11

Step	low	high	mid	list[mid]	Comparison	Action
1	0	7	3	7	11 > 7	low = 4
2	4	7	5	11	11 = 11	Found!

Result: Found at index 5 (only 2 comparisons needed)

With a linear search, this would have taken 6 comparisons.

---

Comparing Linear and Binary Search

Feature	Linear Search	Binary Search
Data must be sorted?	No	Yes
Best case	1 comparison	1 comparison
Worst case	n comparisons	log₂(n) comparisons
Average case	n/2 comparisons	log₂(n) comparisons
Simplicity	Very simple	More complex
Efficiency on large datasets	Slow	Very fast

Example: Searching 1,000,000 Items

• Linear search: Up to 1,000,000 comparisons
• Binary search: Up to 20 comparisons (because log₂(1,000,000) ≈ 20)

This demonstrates why binary search is vastly more efficient for large sorted datasets.

Exam Tip: A common exam question asks you to compare linear and binary search. Always mention: (1) binary search requires sorted data, (2) binary search is more efficient for large datasets, (3) linear search is simpler and works on unsorted data. If asked to "state one advantage of linear search," say it does not require the data to be sorted.

---

When to Use Each Algorithm

Use Linear Search When...	Use Binary Search When...
The data is unsorted	The data is sorted
The dataset is small	The dataset is large
You need a simple solution	You need an efficient solution
The data changes frequently (constant re-sorting is expensive)	The data is static or already sorted

---

Summary

Linear search checks each item one by one and works on any list, but is slow for large datasets. Binary search repeatedly halves the search space and is much faster, but requires sorted data. You must be able to write pseudocode for both algorithms, trace through them with example data, and compare their performance.

---

Extended Study: Searching through a Computational-Thinking Lens

Searching is one of the cleanest illustrations of computational thinking in action. Both linear and binary search are built from the same four-pillar reasoning: decompose the search into "check one element" + "decide where to look next", abstract the data as an array, recognise the pattern of repeated comparison, and express the logic as an algorithm in pseudocode. This section develops that viewpoint with two worked examples and grade-banded model answers.

Decomposition of a search

Any search algorithm can be decomposed into three sub-problems: