How does binary search beat linear search, and how do we compare the efficiency of algorithms?
Topic 3.11/3.17/3.18 Binary Search and Efficiency: binary search finds a value in a sorted list far faster than linear search, and algorithms are compared by efficiency, with some problems being unsolvable or only approximable.
A focused answer to AP CSP Topics 3.11, 3.17 and 3.18, covering linear versus binary search, why binary search needs a sorted list, reasonable versus unreasonable running time, polynomial versus exponential growth, heuristics, and undecidable problems.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
Jump to a section
What this topic is asking
The College Board (Topics 3.11, 3.17 and 3.18) wants you to compare search algorithms and reason about efficiency. You must contrast linear search (check each element in turn) with binary search (repeatedly halve a sorted list), and know that binary search is far faster but requires a sorted list. You also need the idea of reasonable versus unreasonable running time (polynomial versus exponential growth), heuristics (approximate solutions), and that some problems are undecidable (no algorithm can solve them).
Linear search
Binary search
For a sorted list of 1000, binary search needs about 10 comparisons because the list halves: 1000, 500, 250, 125, ... down to 1 in roughly 10 steps. Linear search could need 1000.
Comparing efficiency
Binary search (log) is more efficient than linear search (proportional to n), which is itself far better than exponential algorithms.
Heuristics and undecidable problems
When an exact solution would take unreasonable time, a heuristic provides an approximate, good-enough answer quickly (for example a delivery-route shortcut that is close to optimal). Some problems are undecidable: no algorithm can produce a correct yes/no answer for every possible input. These are limits on what computing can do.
Try this
Q1. Why is binary search faster than linear search on a large sorted list? [2 points]
- Cue. Binary search halves the remaining list each step (about log-base-2 comparisons), while linear search may check every element (up to
n), so binary search examines far fewer elements as the list grows.
Q2. What is a heuristic, and when is one useful? [2 points]
- Cue. A heuristic is an approach that gives a good-enough approximate solution quickly; it is useful when finding the exact best answer would take unreasonable (for example exponential) time.
Exam-style practice questions
Practice questions written in the style of College Board exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
AP 2022 (style)1 marksMultiple choice. A binary search is used to find a value in a sorted list of 1000 elements. Approximately how many elements must it examine in the worst case?
(A) 1000
(B) 500
(C) About 10
(D) 1
Show worked answer →
The answer is (C).
Binary search halves the remaining list each step, so the worst case is about log base 2 of the list size. Log base 2 of 1000 is about 10, so binary search examines roughly 10 elements. (A) 1000 is the worst case for linear search. (B) 500 is the average for linear search. (D) 1 would only happen if the value were found immediately.
Markers reward knowing binary search halves the list each step, giving roughly log-base-2 comparisons, far fewer than linear search.
AP 2021 (style)2 marksFree response (short). Explain why a binary search cannot be used on a list that is not sorted, and what must be true of the list first.
Show worked answer →
A 2-point question on the precondition for binary search.
Point 1: Binary search works by comparing the target to the middle element and discarding half the list based on whether the target is larger or smaller. This only works if the list is sorted (ordered), so that "larger" reliably means "in the right half".
Point 2: If the list is unsorted, the half it discards might contain the target, so the result would be wrong. The list must be sorted first (which itself takes time). A common error is to claim binary search works on any list; it requires order.
Related dot points
- Topic 3.10 Lists: a list is an ordered collection of elements accessed by index; AP CSP lists are 1-indexed and support traversal and modification with APPEND, INSERT and REMOVE.
A focused answer to AP CSP Topic 3.10, covering lists as ordered collections, 1-based indexing in AP CSP pseudocode, accessing elements, traversing with FOR EACH and REPEAT, list operations (APPEND, INSERT, REMOVE, LENGTH), and why lists scale data processing.
- Topic 3.9 Developing Algorithms: an algorithm is a finite set of instructions that accomplishes a task, built by combining sequencing, selection and iteration, and different algorithms can solve the same problem.
A focused answer to AP CSP Topic 3.9, covering what an algorithm is, the three building blocks (sequencing, selection, iteration), expressing algorithms in pseudocode and language, that different algorithms can solve the same problem, and standard list algorithms.
- Topic 3.8 Iteration: iteration (REPEAT n TIMES and REPEAT UNTIL) repeats a block of code, with the number of repetitions controlled by a count or a condition.
A focused answer to AP CSP Topic 3.8, covering REPEAT n TIMES and REPEAT UNTIL loops in AP CSP pseudocode, counting iterations, accumulating values, infinite loops and off-by-one errors, and tracing loop execution.
- Topic 3.15/3.16 Random Values and Simulations: simulations are simplified, abstract models of real phenomena that often use random values to represent variability, trading detail for speed, safety and repeatability.
A focused answer to AP CSP Topics 3.15 and 3.16, covering the RANDOM procedure and generating random values, what a simulation is, why simulations are abstractions, their advantages and limitations, and using randomness to model variability, with worked pseudocode.
- Topic 3.18 Undecidable Problems: some problems cannot be solved by any algorithm for all inputs (undecidable problems), and some solvable problems take unreasonable time, so heuristics give approximate answers.
A focused answer to AP CSP Topic 3.18, covering decidable versus undecidable problems, the limits of computation, the difference between unsolvable and merely slow problems, reasonable versus unreasonable running time, and the role of heuristics.
Sources & how we know this
- AP Computer Science Principles Course and Exam Description — College Board (2025)