OCR A Level CS 2.3.4 Searching Algorithms

What is the purpose of a searching algorithm?

To find a specific element in a data structure, such as an array or list.

What are the two standard searching algorithms in OCR A-Level?

✅ Linear Search
✅ Binary Search

How does linear search work?

It checks each element one by one until it finds the target or reaches the end.

What is the time complexity of linear search?

O(n) – Worst case, it checks every element.

What is an advantage of linear search?

✅ Works on unsorted data.

What is a disadvantage of linear search?

❌ Slow for large data sets.

Pseudocode for linear search:

i = 0

while i < A.length:

if A[i] == x:

return i

else:

i = i + 1

return "Not found"

How does binary search work?

It finds the middle element, checks if it's the target, and then eliminates half of the remaining data.

What is the time complexity of binary search?

O(log n) – It halves the data each step, making it much faster than linear search.

What is a key requirement for binary search?

The data must be sorted.

What is an advantage of binary search?

✅ Much faster than linear search for large data sets.

What is a disadvantage of binary search?

❌ Only works on sorted data.

Pseudocode for binary search:

low = 0

high = A.length - 1

while low <= high:

mid = (low + high) / 2

if A[mid] == x:

return mid

else if A[mid] > x:

high = mid - 1

else:

low = mid + 1

return "Not found"

Comparing Linear and Binary Search

Feature	Linear Search	Binary Search
Best for...	Small datasets or unsorted data	Large datasets, sorted data
Time Complexity	O(n) (Slow)	O(log n) (Fast)
Requires Sorting?	❌ No	✅ Yes
Efficiency	❌ Inefficient for large data	✅ Highly efficient