Comparing Linear and Binary Search

This lesson compares the two standard searching algorithms — linear search and binary search — as required by OCR J277 Section 2.2. The OCR GCSE Computer Science exam frequently asks students to compare these algorithms, so you need to understand the strengths, weaknesses, and appropriate use cases for each.

---

Side-by-Side Comparison

Feature	Linear Search	Binary Search
How it works	Checks each item one by one from the start	Repeatedly divides the sorted data in half
Data requirement	Works on sorted or unsorted data	Data must be sorted
Best case	O(1) — target is the first item	O(1) — target is the middle item
Worst case	O(n) — must check every item	O(log n) — divides the list each time
Average case	O(n/2) ≈ O(n)	O(log n)
Simplicity	Very simple to code and understand	More complex logic with low, high, mid
Memory	Minimal — just a loop counter	Needs variables for low, high, mid
Small datasets	Efficient enough; overhead is low	Overhead of sorting may not be worth it
Large datasets	Very slow	Very fast

---

Efficiency in Practice

Consider searching a list of 1,000 items:

Algorithm	Worst-Case Comparisons
Linear search	1,000
Binary search	~10 (log₂ 1000 ≈ 10)

For 1,000,000 items:

Algorithm	Worst-Case Comparisons
Linear search	1,000,000
Binary search	~20 (log₂ 1,000,000 ≈ 20)

The difference is staggering — binary search is approximately 50,000 times faster than linear search for a million items in the worst case.

OCR Exam Tip: When asked to compare the efficiency of two algorithms, always refer to the number of comparisons or steps needed, not just say one is "faster". Use specific numbers where possible. For example: "For 1000 items, linear search may need up to 1000 comparisons whereas binary search needs at most 10."

---

When to Choose Linear Search

Linear search is the better choice when:

1. The data is unsorted — binary search simply cannot work on unsorted data. If sorting the data first would take longer than a linear search, then linear search is more appropriate.
2. The dataset is small — for a list of, say, 10 items, linear search is fast enough and simpler to implement.
3. You only need to search once — if you are performing a single search on unsorted data, it may be quicker to do a linear search than to sort the data and then use binary search.
4. The data changes frequently — if items are constantly being added or removed, maintaining a sorted list is expensive.

---

When to Choose Binary Search

Binary search is the better choice when:

1. The data is already sorted — no additional cost is needed to prepare the data.
2. The dataset is large — the O(log n) efficiency makes a huge difference.
3. You need to search multiple times — sort the data once, then perform many fast binary searches.
4. Performance matters — in time-critical applications, binary search is far superior.

---

The Cost of Sorting

A key consideration is whether the cost of sorting the data is worth it. If you have unsorted data and need to perform a single search:

• Linear search on unsorted data: O(n)
• Sort + binary search: O(n log n) + O(log n) ≈ O(n log n)

In this case, linear search is actually faster overall. However, if you need to search the same data many times:

• k linear searches: O(k × n)
• Sort once + k binary searches: O(n log n) + O(k × log n)

For large k, the binary search approach wins dramatically.

---

Exam-Style Comparison Questions

Example 1: Short Answer

Question: State one advantage and one disadvantage of binary search compared to linear search. (2 marks)

Answer:

• Advantage: Binary search is much more efficient for large datasets — O(log n) compared to O(n) for linear search, meaning far fewer comparisons are needed.
• Disadvantage: Binary search requires the data to be sorted first, whereas linear search works on unsorted data.

Example 2: Scenario-Based

Question: A school stores 2,000 student records sorted alphabetically by surname. A teacher needs to find a student's record. Which search algorithm would be most appropriate? Explain your answer. (3 marks)

Answer: Binary search would be most appropriate because:

1. The data is already sorted alphabetically.
2. With 2,000 records, binary search would need at most approximately 11 comparisons (log₂ 2000 ≈ 11).
3. Linear search could need up to 2,000 comparisons in the worst case, making it much slower.

OCR Exam Tip: In scenario questions, always link your answer to the specific details given. Do not just state generic advantages — explain why they apply to the given situation.

---

Common Exam Mistakes to Avoid

1. Saying binary search is "always better" — this is wrong. Linear search is better for unsorted or very small datasets.
2. Forgetting that binary search needs sorted data — this is the most common omission.
3. Not explaining how efficiency scales — use numbers like "10 comparisons vs 1,000" rather than vague statements.
4. Confusing the algorithms — make sure you can clearly describe how each one works step by step.

---

Summary

• Linear search: simple, works on any data, but slow for large lists (O(n)).
• Binary search: fast for large sorted lists (O(log n)), but requires sorted data.
• Choose based on data size, whether data is sorted, and how many searches you need.
• In exams, always justify your choice with reference to the specific scenario.

OCR Exam Tip: A 4-mark comparison question typically expects two points about linear search and two about binary search. Structure your answer clearly, e.g. "Linear search... whereas binary search..." to make the comparison explicit.

---

Scenario Practice: Matching Algorithm to Situation

For each scenario below, decide which search algorithm is more appropriate and justify your answer in one sentence.

Scenario A: A phone book lists 10,000 entries sorted alphabetically by surname. You want to find "Taylor". Best choice: Binary search. The data is sorted and the list is large; at most 14 comparisons are needed instead of up to 10,000.

Scenario B: A spreadsheet contains 30 pupils' scores in the order they were entered (unsorted). You need to find a score of 85. Best choice: Linear search. The data is unsorted and the list is small, so the overhead of sorting first is not worth it.

Scenario C: A website displays today's live scores (constantly changing) in order of fixture kick-off time. You want to find Chelsea's score. Best choice: Linear search. The data is not sorted by team name and changes frequently, so maintaining a sorted list would be expensive.