Searching Algorithms

GCSE Computer Science · Algorithms

Searching Algorithms

Searching algorithms find a specific item within a data structure. You need to know linear search and binary search for the exam.

---

Linear Search

Linear search checks each element in turn from the start until the target is found or the list ends.

Pseudocode

FUNCTION linearSearch(list, target)
    FOR i = 0 TO LEN(list) - 1
        IF list[i] == target THEN
            RETURN i
        END IF
    END FOR
    RETURN -1
END FUNCTION

Key Properties

Property	Detail
Time complexity (best)	O(1) — target is the first element
Time complexity (worst)	O(n) — target is last or absent
Time complexity (average)	O(n)
Data requirement	Works on any list (sorted or unsorted)
Space complexity	O(1) — no extra storage needed

How It Works (Walkthrough)

Given the list [5, 3, 8, 1, 9], searching for 8:

1. Compare 5 with 8 — no match

2. Compare 3 with 8 — no match

3. Compare 8 with 8 — match found at index 2

---

Binary Search

Binary search repeatedly halves the search space by comparing the target with the middle element. The list must be sorted first.

Pseudocode

FUNCTION binarySearch(list, target)
    low = 0
    high = LEN(list) - 1
    WHILE low <= high
        mid = (low + high) DIV 2
        IF list[mid] == target THEN
            RETURN mid
        ELSE IF list[mid] < target THEN
            low = mid + 1
        ELSE
            high = mid - 1
        END IF
    END WHILE
    RETURN -1
END FUNCTION

Key Properties

Property	Detail
Time complexity (best)	O(1) — target is the middle element
Time complexity (worst)	O(log n) — halves each step
Time complexity (average)	O(log n)
Data requirement	List must be sorted
Space complexity	O(1) iterative, O(log n) recursive

How It Works (Walkthrough)

Given the sorted list [1, 3, 5, 8, 9, 12, 15], searching for 9:

1. low=0, high=6, mid=3 → list[3]=8, 8 < 9 → low=4

2. low=4, high=6, mid=5 → list[5]=12, 12 > 9 → high=4

3. low=4, high=4, mid=4 → list[4]=9 — match found at index 4

---

Big O Notation

Big O notation describes how the time or space an algorithm uses grows as the input size (n) increases. It measures the worst-case scenario.

Notation	Name	Example
O(1)	Constant	Accessing an array element by index
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search
O(n log n)	Linearithmic	Merge sort
O(n²)	Quadratic	Bubble sort

Efficiency ranking (best to worst): O(1) → O(log n) → O(n) → O(n log n) → O(n²)

---

Comparison Table

Feature	Linear Search	Binary Search
Sorted data needed?	No	Yes
Best case	O(1)	O(1)
Worst case	O(n)	O(log n)
Speed on large data	Slow	Fast
Implementation	Simple	More complex
When to use	Small or unsorted lists	Large sorted lists

---

Exam Tips

If asked to trace an algorithm, show each step clearly in a table with the values of all variables
Binary search is much faster on large datasets but requires sorting first — the sort itself costs time
Always state that binary search needs a sorted list — this is a commonly tested point
When comparing algorithms, discuss time complexity, data requirements, and suitability for the scenario given

Searching Algorithms