Unit 4 Cycle 2 Day 19: I/II/III: Search and Sort Properties
Share
I/II/III: Search and Sort Properties
Section 4.6 — Searching
Key Concept
I/II/III search and sort properties questions test fundamental characteristics: linear search works on unsorted data (O(n)), binary search requires sorted data (O(log n)), selection sort always makes the same number of comparisons, insertion sort is fastest on nearly-sorted data, and both sorts are O(n^2) in the worst case. Each statement asserts a property that you must verify. The AP exam tests whether you confuse properties between algorithms or incorrectly apply big-O analysis to specific cases.
Consider the following statements.
Which are true?
Answer: (A) I and III only
I: TRUE. No preconditions.
II: FALSE. For tiny arrays, linear can be faster. Binary also requires sorted data.
III: TRUE. Each pass places the minimum in its final spot.
Why Not the Others?
(B) II is false for small arrays and unsorted data.
(C) II is false.
(D) II is false.
Common Mistake
Binary search is O(log n) but requires sorted data. For one-time search on unsorted data, sorting cost (O(n log n)) makes linear search more efficient.
AP Exam Tip
Binary search advantage applies to repeated searches on sorted data. Single search on unsorted data favors linear search.