Compare the time complexity of both algorithms and explain when to use each
Apply binary search to a given sorted list and show the midpoint at each step
Linear Search
Linear Search Algorithm
function linearSearch(arr, target) for i ← 0 to len(arr)-1 if arr[i] = target then return i endif next i return -1 // not found endfunction
Complexity
Best case: O(1) — target at index 0 Average: O(n/2) = O(n) Worst case: O(n) — not found or last element Works on unsorted data
When to Use
Small datasets where sorting cost is unjustified; unsorted data where binary search is not possible; linked lists where random access is expensive; when searching only once (no benefit to sorting)
Binary Search
Binary Search Algorithm
function binarySearch(arr, target) lo ← 0 : hi ← len(arr)-1 while lo ≤ hi mid ← (lo+hi) div 2 if arr[mid] = target then return mid elif arr[mid] < target then lo ← mid + 1 else hi ← mid - 1 endif endwhile return -1 endfunction
Binary Search Trace
Tracing Binary Search
Search for 14 in sorted array: [2, 5, 7, 10, 14, 19, 23, 30]
Step
lo
hi
mid
arr[mid]
Action
1
0
7
3
10
10<14 → lo=4
2
4
7
5
19
19>14 → hi=4
3
4
4
4
14
Found! Return 4
Only 3 comparisons to find 14 in 8 elements. Linear search would take up to 5 comparisons. For larger arrays, this gap grows dramatically — log₂(1,000,000) = 20 vs up to 1,000,000 for linear.
Comparison
Linear vs Binary Search: Key Differences
Linear Search
Data requirement: none (works on unsorted data) Time complexity: O(n) worst case Best for: small or unsorted datasets Implementation: simple loop Memory: O(1)
Binary Search
Data requirement: must be sorted Time complexity: O(log n) worst case Best for: large sorted datasets Implementation: more complex Memory: O(1) iterative, O(log n) recursive
If data is already sorted and will be searched many times, binary search is worth the extra complexity. If data is unsorted and only searched once, the sorting cost may exceed the benefit.
Recursive Binary Search
Binary Search: Recursive Approach
function binSearch(arr, target, lo, hi) if lo > hi then return -1 // base case: not found mid ← (lo+hi) div 2 if arr[mid] = target then return mid elif arr[mid] < target then return binSearch(arr, target, mid+1, hi) else return binSearch(arr, target, lo, mid-1) endif endfunction
Recursive approach uses O(log n) stack space — each call adds a frame. Iterative approach uses O(1) space. For very large datasets, the iterative approach avoids potential stack overflow and is generally preferred in practice.
Exam Practice
OCR H446 Style · 4 marks
Use binary search to find the value 31 in the sorted list [4, 11, 19, 25, 31, 38, 44, 50, 58]. Show the mid value and remaining search space at each step. State how many comparisons were needed.
Using wrong midpoint calculation — mid = (lo + hi) div 2 (integer division). Do NOT round up — always round down (floor). On a trace, calculating mid incorrectly cascades errors through every subsequent step, losing all following marks.
!
Not updating lo or hi correctly — when target > arr[mid], lo becomes mid+1 (not mid). When target < arr[mid], hi becomes mid-1 (not mid). Using mid instead of mid±1 can cause an infinite loop and is penalised in OCR mark schemes.
!
Claiming binary search is always better — it requires sorted data, which has a cost. For a single search on unsorted data, linear search is O(n) while sorting + binary search is O(n log n) + O(log n) — linear search is faster. Binary search is only better when multiple searches are performed on already-sorted data.