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: