B2.4.2 · Programming algorithms
Linear and binary search
By the end you can
Construct, trace, and compare linear search (O(n)) and binary search (O(log n)) on ordered arrays.
Searching is one of the most frequent computational tasks in software engineering. Given a target value, a search algorithm scans an array and either returns the index of the matching element or reports that it is absent.
Linear search ($O(n)$)#
starts at the beginning of the array and examines each element in sequence until the target is found or the end of the array is reached:
- No ordering requirement: Works on unsorted arrays.
- Simplicity: Very few lines of code; low overhead for small arrays ($n < 20$).
- Slow on large data: For $1,000,000$ elements, linear search takes up to $1,000,000$ comparisons in the worst case ($O(n)$).
Binary search ($O(\log n)$)#
is a divide-and-conquer algorithm that operates on a sorted array:
- Set
low = 0andhigh = length - 1. - Find the middle index:
mid = floor((low + high) / 2). - If
arr[mid] == target, search succeeds! - If
arr[mid] < target, target must be in the right half; discard left half by settinglow = mid + 1. - If
arr[mid] > target, target must be in the left half; discard right half by settinghigh = mid - 1. - Repeat while
low ≤ high. Iflow > high, the target is absent.
Step 1 of 4: Middle index 5 (45) is less than 67. Discard left half; search new range [6 .. 10].
Check yourself
Linear and binary search
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
3 questions · 8 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Compare linear search and binary search in terms of preconditions, algorithm mechanism, and time complexity.
[4]Compare: Similarities and differences, about both things, point by point.
2.Calculate the maximum number of comparisons needed for binary search to find a key or determine it is absent in a sorted array of 1,000,000 elements.
[2]Calculate: Work out the number, showing the working.
3.Explain why binary search cannot be performed directly on an unsorted array.
[2]Explain: Give reasons: say what happens AND why, or how one thing causes another.
In a nutshell
- Linear search checks elements sequentially from index 0; operates on unsorted data with O(n) worst-case time.
- Binary search requires a sorted array; compares the target with the middle element and halves the search range (O(log n)).
- In an array of 1,000,000 items, linear search requires up to 1,000,000 comparisons while binary search requires at most 20 comparisons.
- Binary search is ideal for static or infrequently modified datasets where sorting costs are amortized over many lookups.