Lesson 4.14: Searching Algorithms
AP CSA Hub Unit 4 4.1 ▼ Lesson Ex 1 Ex 2 Quiz 4.2 ▼ Lesson Ex 1 Ex 2 Quiz 4.3 ▼ Lesson Ex 1 Ex 2 Quiz 4.4 ▼ Lesson Ex 1 Ex 2 Quiz 4.5 ▼ Lesson Ex 1 Ex 2 Quiz 4.6 ▼ Lesson Ex 1 Ex 2 Quiz 4.7 ▼ Lesson Ex 1 Ex 2 Quiz 4.8 ▼ Lesson Ex 1 Ex 2 Quiz 4.9 ▼ Lesson Ex 1 Ex 2 Quiz 4.10 ▼ Lesson Ex 1 Ex 2 Quiz 4.11 ▼ Lesson Ex 1 Ex 2 Quiz 4.12 ▼ Lesson Ex 1 Ex 2 Quiz 4.13 ▼ Lesson Ex 1 Ex 2 Quiz 4.14 ▼ Lesson Ex 1 Ex 2 Quiz 4.15 ▼ Lesson Ex 1 Ex 2 Quiz 4.16 ▼ Lesson Ex 1 Ex 2 Quiz 4.17 ▼ Lesson Ex 1 Ex 2 Quiz
Lesson 4.14: Searching Algorithms
🕒 40-50 min
·
10 Practice Questions
·
Linear Search · Binary Search · Comparisons
What You'll Learn
- Implement linear search, which checks elements in order and works on data in any order.
- Implement binary search, which requires sorted data and repeatedly halves the search range.
- Explain why binary search depends on sorted input and what happens when that precondition is violated.
- Compare the number of comparisons linear search and binary search make on the same data.
Key Vocabulary
| Term | Definition |
|---|---|
| linear search | Checking each element in order from the start until a match is found or the array ends. |
| binary search | Repeatedly checking the middle of a sorted range and discarding the half that cannot contain the target. |
| precondition | A condition an algorithm assumes is already true before it runs. Binary search's precondition is that the data is sorted. |
| comparison | One check of a target value against an element. The standard way to measure how much work a search does. |
Linear Search
Linear search checks elements one at a time from the front. It makes no assumption about order, which is exactly why it works on any data.
int index = -1;
for (int i = 0; i < data.length && index == -1; i++) {
if (data[i] == target) {
index = i;
}
}Binary Search
Binary search checks the middle of the current range. If the middle is not the target, the half that CANNOT contain it is discarded entirely.
int low = 0;
int high = data.length - 1;
int index = -1;
while (low <= high && index == -1) {
int mid = (low + high) / 2;
if (data[mid] == target) {
index = mid;
} else if (data[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}⚠️ Binary Search Needs Sorted Data
Every "go left" or "go right" decision assumes the data is in order. Run on unsorted data, that assumption is false, and the result becomes unreliable: a real match can be discarded along with the wrong half.
Comparing the Cost
📌 Halving Beats Scanning, at Scale
Linear search's worst case grows with the length of the array. Binary search's worst case grows with the base-2 logarithm of the length, which is dramatically smaller once the array gets large: a million elements takes roughly 20 comparisons for binary search, not a million.
Practice Questions
MCQ 1
Which search algorithm works correctly on data in ANY order?
A Binary search only
B Both, identically
C Neither
D Linear search
✓ D. Linear search makes no assumption about order at all, which is exactly why it tolerates any arrangement of the data.
MCQ 2
What does binary search require of its input before it runs?
A The data must already be sorted
B Nothing special
C The data must be all positive
D The array must have an even length
✓ A. Sorted order is binary search's precondition; every halving decision depends on it.
MCQ 3
How many comparisons does binary search make to find target=6 in [2,4,6,8,10]?
A 1
B 2
C 3
D 5
✓ A. low=0, high=4, mid=2, data[2]=6: an immediate match on the very first comparison.
MCQ 4
What happens when binary search's halving logic is run on UNSORTED data?
A It still works correctly, just slower
B It throws a compile error
C Results become unreliable, because each decision to discard a half assumes an order that is not actually there
D It automatically sorts the data first
✓ C. Nothing about the algorithm checks whether its assumption holds; it just proceeds on it, which is why the result can be wrong.
MCQ 5
As array length n grows very large, which is true of the two algorithms' worst-case comparison counts?
A Linear search and binary search always take the same number of comparisons
B Neither count depends on n at all
C Binary search always takes more comparisons than linear search
D Linear search's worst case grows with n; binary search's worst case grows with log base 2 of n, dramatically smaller for large n
✓ D. This gap is the entire reason binary search is worth the precondition of sorted data.
Mastery: Searching Algorithms
MCQ 6
How many comparisons does binary search make to find target=13 in [1,3,5,7,9,11,13]?
A 1
B 2
C 3
D 7
✓ C. mid=3 (value 7, low), then mid=5 (value 11, low), then mid=6 (value 13, match): 3 comparisons.
MCQ 7
What does binary search return for target=4 on [1,3,5,7,9,11,13], and how many comparisons does it make?
A index 3, 1 comparison
B -1 (not found), 3 comparisons
C -1 (not found), 7 comparisons
D index -1, 0 comparisons
✓ B. mid=3 (value 7, high goes down), mid=1 (value 3, low goes up), mid=2 (value 5, high goes down): the range empties after 3 comparisons, reporting -1.
MCQ 8
Linear search scans [9,7,5,3,1] for target=1. How many comparisons does it make?
A 1
B 4
C 5
D 0
✓ C. It checks 9, 7, 5, 3, then 1, five comparisons before the match at the last position.
MCQ 9
A search must run on data whose order can change between calls and cannot be assumed sorted. Which search is the only reliably correct choice?
A Linear search, because it makes no assumption about order
B Binary search, because it is always faster
C Neither works on data of unknown order
D Binary search, run twice to be safe
✓ A. Speed is irrelevant if the answer can be wrong, and binary search's correctness depends on an assumption that is not guaranteed here.
MCQ 10
Why is data in this lesson's exercises explicitly given ALREADY SORTED, rather than asking you to sort it first?
A Sorting is not part of the AP CSA curriculum
B Binary search's precondition is sorted data, and Sorting Algorithms is its own separate lesson right after this one; this lesson isolates the search skill from the sort skill
C Sorting an array is always a compile error
D There is no real reason; it is arbitrary
✓ B. Searching and sorting are taught as separate CED topics on purpose, and this lesson's exercises reflect that separation.
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.
Typically responds within 24 hours
✓
Message Sent!
Thanks for reaching out. I'll get back to you within 24 hours.
Prefer email? Reach me directly at [email protected]