Binary search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72]. What is the first midpoint?
- 9 items, indices 0 to 8.
- Midpoint index (0 + 8) DIV 2 = 4.
- Value 16; 23 > 16 so search the right half.
Answer 16 (index 4)
A-level Computer Science revision · Data structures and algorithms
Linear search checks each item in turn: it works on unsorted data and is O(n). Binary search compares the target with the middle item of a sorted list and discards half each time: O(log n). For n items, binary search needs at most about log₂n + 1 comparisons.
Watch out Binary search does not work on unsorted data.
Binary search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72]. What is the first midpoint?
Answer 16 (index 4)
What is the maximum number of comparisons binary search needs to search a sorted list of 1000 items?
Which search can be used on an unsorted list?
What is the worst-case time complexity of linear search?
A-level Computer Science Pro, OCR H446
£119 once
Price rises to £199 on 1 January. Save £80 by joining before then.
At least 12 months of access
No VAT is charged.