How does a binary search work?
A binary search finds an item in a sorted list by repeatedly checking the middle item. If the middle item is the target, stop. If the target is smaller, discard the upper half; if larger, discard the lower half. Repeat until the item is found or no items remain. Its time complexity is O(log n). Example: Find 23 in [3, 8, 15, 23, 42, 57, 61]. Middle (index 3) = 23 Answer: Found at index 3 in one comparison.
Binary search is a divide-and-conquer algorithm that only works on sorted data. Each comparison halves the search space, so a list of 1 000 items needs at most about 10 comparisons. At A Level, compare it with linear search, trace it with low, high and mid pointers, and state its O(log n) complexity.
Worked example
Use a binary search to find 57 in [3, 8, 15, 23, 42, 57, 61] (indices 0 to 6).
- low = 0, high = 6, mid = (0 + 6) ÷ 2 = 3. Item 23 < 57, so set low = 4.
- low = 4, high = 6, mid = (4 + 6) ÷ 2 = 5. Item 57 = target.
- Stop: the item has been found.
- Comparisons made: 2.
Answer: 57 is found at index 5 after 2 comparisons.
Want one-to-one support?
One-to-one online tuition can help you build confidence in your subject. Find a tutor who teaches your course.
Find a TutorLearn face to face in Glasgow
Prefer in-person lessons? Visit the ExpertTutor Glasgow Southside centre.
See the centre