AP CSP Linear Search
AP CSP Linear Search: Complete Guide (2025‑2026)
Linear search checks each element of a list one at a time, in order, until it finds the target or exhausts the list. It works on any list — sorted or unsorted — which is both its strength and its limitation. The AP CSP exam tests linear search implementation, how many comparisons it makes in best/worst cases, and how it differs from binary search.
Contents
How Linear Search Works
Linear search found 42 at position 4 after 4 comparisons. If 42 were not in the list, it would check all 6 elements before concluding it was not found.
Linear vs. Binary Search
- Works on sorted AND unsorted lists
- Checks elements one by one from start
- Best case: 1 comparison (target is first)
- Worst case: N comparisons (not found)
- Simple to implement, slow for large lists
- Requires SORTED list — does not work unsorted
- Eliminates half the remaining list each step
- Best case: 1 comparison (target is middle)
- Worst case: log2(N) comparisons
- More complex, dramatically faster for large lists
Code Trace Gauntlet
How many comparisons before the loop ends? What does found equal?
true 5=8? NO. 12=8? NO. 8=8? YES → found=true. 3=8? NO. 19=8? NO. Loop finishes (all elements). found=true. Note: this implementation checks ALL elements even after finding it — no early exit.
5 is not in the list. What displays and how many comparisons ran?
false 4 comparisons (all elements checked). 4=5? NO. 7=5? NO. 2=5? NO. 9=5? NO. Loop ends, found stays false.
How many comparisons before returning?
true 1=2? NO. 2=2? YES → RETURN true immediately. Only 2 comparisons. Early exit stops checking remaining elements.
What position (1-based) is 15 at?
3 pos=1: 8=15? NO, pos=2. 3=15? NO, pos=3. 15=15? YES → RETURN 3.
Spot the Bug
If target is not in the list, the loop finishes without returning anything. Fix: add RETURN false after the loop ends.
This displays false for EVERY non-matching element, not just when the target is absent. A 5-element list where target is at position 5 would print false 4 times then true once. Fix: set a found flag to true on match, display found after the loop.
Common Exam Pitfalls
This is its advantage over binary search. You can run linear search on any list, in any order.
If the target is not in the list, every element is checked. A 10-element list requires 10 comparisons in the worst case.
The flag-based version (found ← true) continues checking remaining elements after finding the match. The RETURN version exits immediately.
If the list has duplicate values matching the target, linear search finds the FIRST occurrence (lowest index) and stops there (in early-exit versions).
Check for Understanding
1. Linear search on a list of 8 elements. The target is the 8th element. How many comparisons are made?
- 1
- 4
- 7
- 8
2. A list is [3, 9, 1, 7, 4]. Linear search looks for 7. How many comparisons before finding it?
- 3
- 4
- 5
- 2
3. Which statement about linear search is correct?
- Linear search requires a sorted list.
- Linear search always makes N comparisons regardless of target location.
- Linear search works on any list, sorted or unsorted.
- Linear search is faster than binary search for large sorted lists.
4. A linear search finds the target at position 1 (the very first element). How many comparisons were made?
- 0
- 1
- N
- N/2
5. Which procedure correctly implements linear search?
FOR EACH x IN lst
RETURN x = targetFOR EACH x IN lst
IF x = target
RETURN true
RETURN falseFOR EACH x IN lst
IF x > target
RETURN false
RETURN trueIF lst[1] = target
RETURN true
RETURN false
6. Consider: I. Linear search checks elements sequentially from start to end. II. Linear search requires the list to be sorted. III. The worst case for linear search is when the target is not in the list.
- I only
- I and III only
- I, II, and III
- II and III only
7. A list has 100 elements. The target is not in the list. How many comparisons does linear search make?
- 50
- 99
- 100
- 7 (log2 100)
8. Why would a programmer choose linear search over binary search?
- Linear search is always faster.
- The list is unsorted and sorting is not an option.
- Linear search uses less memory.
- Linear search works on numbers but not strings.
9. lst ← [2,4,6,8,10]
found ← false
FOR EACH n IN lst
IF n MOD 2 = 0
found ← true
DISPLAY(found)
This is a linear search for:
- The value 2
- Any even number
- All even numbers
- The number 10
10. A linear search returns -1 when the target is not found and the 1-based index when found. What does it return for target=5 in list [9,5,3,5,1]?
- 1
- 2
- 4
- -1
How the AP Exam Tests This
- Count comparisons made by linear search for a specific target position
- Determine whether linear search or binary search is appropriate given list properties
- Trace a linear search procedure and report the return value
- I/II/III: which statements about linear search properties are correct
- Identify a bug in a linear search implementation (missing false return, wrong condition)
FAQ
Get in Touch
Whether you're a student, parent, or teacher — I'd love to hear from you.
Just want free AP CS resources?
Enter your email below and check the subscribe box — no message needed. Students get daily practice questions and study tips. Teachers get curriculum resources and teaching strategies.
Message Sent!
Thanks for reaching out. I'll get back to you within 24 hours.
tanner@apcsexamprep.com
Courses
AP CSA, CSP, & Cybersecurity
Response Time
Within 24 hours
Prefer email? Reach me directly at tanner@apcsexamprep.com