Binary search — AQA A-Level Computer Science

A binary search is an efficient divide-and-conquer search algorithm with a time complexity of O(log n) that repeatedly halves the search space to locate a target value. It strictly requires the underlying data structure to be sorted and support random access via index pointers.

Binary search explained

Binary search finds a target in a sorted list by repeatedly comparing it with the middle element and discarding the half that cannot contain the target.

Read the full explanation

Tracing the algorithm means following each step: identify the lower and upper bounds, calculate the middle index, compare, and update the bounds, until the target is found or the bounds cross. Analysing the time taken means showing that each comparison halves the remaining search space, so at most about log₂ n comparisons are needed, giving O(log n) time complexity. For example, a sorted list of 1024 items needs at most about 10 comparisons, since 2¹⁰ = 1024. Learners should be able to trace a search on a small sorted list, count the comparisons, and justify the logarithmic growth rate.

Your focus

Know and be able to trace and analyse the time

Which command word is this?

Follow the execution of the algorithm step-by-step, recording variable states (low, high, mid, and array[mid]) at each iteration in an orderly table.

Binary search exam tips

Topic Overview

Binary search is a fundamental search algorithm taught in AQA A-Level Computer Science that illustrates the divide-and-conquer design paradigm. By repeatedly halving the active search interval, the algorithm dramatically cuts the number of comparisons required compared to linear scanning.

Understanding binary search provides crucial insight into logarithmic algorithmic complexity O(log n) and recursion. It bridges data structures and algorithmic efficiency, demonstrating why ordered arrays or balanced search trees are essential for handling large-scale computational queries.

Key Concepts

→Preconditions: The dataset must be stored in a sorted, contiguous, or directly indexable data structure that supports O(1) random access.
→Divide and Conquer: In each pass, the search interval is halved by comparing the search target against the element at the midpoint index.
→Pointer Adjustment: Pointers representing boundaries ('low' and 'high') must be updated using integer division and offset by 1 ('mid - 1' or 'mid + 1') to prevent infinite loops.
→Time and Space Complexity: Best-case time is O(1), average and worst-case time is O(log n). Iterative implementations require O(1) auxiliary space, whereas recursive versions require O(log n) space due to call stack frames.

Marking Points

Describes the steps of binary search: find the middle element, compare, then discard the half that cannot hold the target.
Traces a search on a sorted list, showing the bounds and middle index at each step.
Explains that the search space halves at each comparison.
States that the worst-case time complexity is O(log n) and relates the number of comparisons to log₂ n.

Examiner Tips

💡When tracing, write down the low, high and mid values at every step so the working can be followed.
💡Show the halving of the search space explicitly to justify the O(log n) complexity.
💡Check that you have stated the list must be sorted, as this is a required condition of the algorithm.
💡Always write out trace tables explicitly showing columns for 'low', 'high', 'mid', and 'array[mid]' when asked to trace this algorithm in AQA Paper 1.
💡In pseudocode questions, clearly handle the base condition where the item is not present (i.e., 'low > high' or 'start > end') to avoid infinite recursion or looping.
💡When asked for worst-case comparisons, remember the formula is floor(log2(n)) + 1 comparisons.

Common Mistakes

Applies binary search to an unsorted list; correct by stating that the list must be sorted for the halving to be valid.
Miscalculates the middle index when the bounds sum to an odd number; correct by using integer division consistently and rechecking the bounds after each update.
States that the number of comparisons is n/2; correct by showing that the search space halves each time, so the count is about log₂ n.
Believing binary search can be executed on any collection: Students often forget that binary search requires both sorted order and direct index access; it cannot run at O(log n) on unordered lists or singly linked lists.
Using real division for midpoint calculation: Using floating-point division (e.g., 7 / 2 = 3.5) causes index errors; integer division (DIV or //) must always be used.
Assuming binary search is always superior to linear search: For very small arrays (e.g., n < 10) or unsorted lists requiring a single query, linear search is simpler and avoids the overhead of sorting.

Revision Plan

1Day 1-2: Master the manual trace of binary search using trace tables on arrays of odd and even lengths, including scenarios where the item is absent.
2Day 3-4: Write and debug both iterative and recursive implementations in your chosen programming language (Python, C#, or VB.NET).
3Day 5: Practice formal Big-O derivations comparing linear search O(n) and binary search O(log n), focusing on why the search space halves every iteration.
4Day 6-7: Complete past AQA exam questions covering algorithm tracing, pseudocode completion, and trade-off analysis between search methods.

Exam Question Types

📋Trace Table Questions: Completing rows for low, high, and mid index pointers to demonstrate how an array is searched for a specific target.
📋Pseudocode Writing / Completion: Writing an iterative or recursive binary search function, including correct termination conditions when an item is not found.
📋Comparative Analysis / Essay Questions: Evaluating whether to use linear search or binary search given a scenario with dynamically updated or unsorted data.

Command Word Expectations (AQA)

Trace

Follow the execution of the algorithm step-by-step, recording variable states (low, high, mid, and array[mid]) at each iteration in an orderly table.

Explain

Set out the reasons or computational mechanisms clearly. For example, explain how the divide-and-conquer principle reduces time complexity to O(log n).

Compare

Identify both similarities and differences between two algorithms (e.g., binary search vs. linear search), focusing on preconditions, best/worst time complexities, and data structure constraints.

How Students Lose Marks (Examiner Pitfalls)

Pitfall: Forgetting that a binary search strictly requires an ordered list, or assuming that performing a sort first always makes binary search faster than linear search for a single query.

❌ Weak Answer (Loses Marks):Binary search is always faster than linear search because its time complexity is O(log n), so you should always use it on any array.

Example improved answer:Binary search has a worst-case time complexity of O(log n), making it significantly more efficient than linear search with O(n) for large lists. However, it requires the array to be sorted. If an unsorted array is searched only once, sorting it first takes O(n log n), meaning an overall O(n log n) cost, which is less efficient than performing a single linear search at O(n).

Examiner Tip: Always specify that the precondition of a binary search is that the dataset must be sorted and indexed. Account for the cost of sorting when comparing overall algorithm efficiencies.

Pitfall: Incorrectly calculating the midpoint pointer or failing to adjust pointers by plus or minus one, which leads to infinite loops in recursive or iterative code traces.

❌ Weak Answer (Loses Marks):To narrow down the list, midpoint = (low + high) / 2, and then high = midpoint.

Example improved answer:The midpoint index is calculated using integer division: mid = (low + high) DIV 2. When the target value is less than array[mid], the high pointer must update to mid - 1. When the target value is greater, the low pointer must update to mid + 1. Omitting the +/- 1 offset can cause an infinite loop if the search item is absent.

Examiner Tip: State clearly whether you are using 0-based or 1-based indexing, and show the explicit evaluation of DIV (integer division) at each step of a trace table.

Step-by-Step Worked Solutions

Question: An array contains the following 9 elements: [3, 7, 12, 19, 24, 31, 45, 58, 62]. Trace a binary search to determine whether the value 45 is present in the list using 0-based indexing. For each iteration, state the low, high, and mid index values, along with the value examined.

1.Step 1: Set low = 0 and high = 8. Calculate mid = (0 + 8) DIV 2 = 4. Examine array[4] which contains 24. Since 45 > 24, discard the lower half by setting low = mid + 1 = 5.
2.Step 2: Low = 5, high = 8. Calculate mid = (5 + 8) DIV 2 = 13 DIV 2 = 6. Examine array[6] which contains 45.
3.Step 3: Compare array[6] to target value. array[6] == 45. The target value is found at index 6, so terminate the search and return index 6.

Final Answer: Target 45 found at index 6 after 2 comparisons (Iteration 1: low=0, high=8, mid=4, value=24; Iteration 2: low=5, high=8, mid=6, value=45).

Active Recall Memory Test

What is the worst-case time complexity of binary search, expressed in Big-O notation?

Key Fact: O(log n)

What two conditions must be met by a dataset before a binary search can be applied?

Key Fact: The data must be ordered (sorted) and stored in an indexable data structure that allows direct/random access.

What condition indicates in code that the binary search has concluded without finding the target value?

Key Fact: The 'low' pointer becomes greater than the 'high' pointer (low > high).

What is the primary difference in space complexity between an iterative binary search and a recursive binary search?

Key Fact: Iterative binary search uses O(1) auxiliary space, whereas recursive binary search uses O(log n) auxiliary space due to call stack frames.

Frequently Asked Questions

Why does binary search use integer division instead of regular division?

Binary search calculates index locations in an array, which must always be whole integers. Regular division can produce a floating-point number (such as index 3.5 when dividing 7 by 2), which is invalid for array indexing. Using integer division (DIV or //) truncates the decimal part, consistently returning a valid integer index.

Can binary search be implemented using recursion?

Yes, binary search is naturally recursive because each step solves a smaller subproblem of the exact same nature. The recursive function takes the array, the search item, and boundary indices (low and high) as parameters. However, the recursive approach uses O(log n) auxiliary memory on the call stack, whereas the iterative while-loop approach uses O(1) memory.

How do you calculate the maximum number of comparisons for a binary search?

The maximum number of comparisons for an array of size n in the worst case is calculated using floor(log2(n)) + 1, or ceil(log2(n + 1)). For example, for a list of 16 items, log2(16) = 4, giving a maximum of 5 comparisons to conclude whether an item exists. You can also find the smallest power of 2 that is greater than or equal to n.

Is binary search always better than linear search?

Binary search is much faster for large, sorted datasets because of its O(log n) complexity versus O(n) for linear search. However, binary search requires the list to be sorted first. If you have an unsorted list that you only need to search once, sorting it takes O(n log n), which makes linear search at O(n) faster overall.

Binary search explained

Your focus

Which command word is this?

Binary search exam tips

More AQA A-Level Computer Science topics

Cookies on MasteryMind