Unit 4 Cycle 2 Day 6: Binary Search Precondition
Share
Binary Search Precondition
Section 4.6 — Searching
Key Concept
Binary search has a critical precondition: the array must be sorted. Applying binary search to an unsorted array produces unpredictable results — it may return a wrong index, miss existing elements, or appear to work for some inputs but fail for others. The AP exam tests this precondition by presenting unsorted arrays and asking what binary search returns, or by asking what must be true about the array before binary search can be used. Always verify that the data is sorted before applying binary search.
A student uses binary search on the following array.
What is the problem?
Answer: (A) Binary search requires a sorted array; results are unpredictable.
Binary search assumes sorted data. On unsorted data, it may eliminate the half containing the target, returning wrong results without error.
Why Not the Others?
(B) It may miss the target entirely, not just find it slowly.
(C) No exception is thrown; the algorithm runs but gives unreliable results.
(D) Binary search REQUIRES sorted data as a precondition.
Common Mistake
Binary search on unsorted data is a logic error, not a runtime error. The algorithm completes but may return incorrect results.
AP Exam Tip
Binary search precondition: array MUST be sorted. No precondition for linear search.