Unit 4 Cycle 1 Day 17: Binary Search Tracing
Share
Binary Search Tracing
Section 4.6 — Searching
Key Concept
Binary search requires a sorted array and works by repeatedly halving the search space. It compares the target to the middle element: if equal, the target is found; if less, search the left half; if greater, search the right half. Each step eliminates half the remaining elements, making it O(log n). The AP exam tests binary search by asking you to trace the algorithm through specific sorted arrays, counting comparisons and identifying which elements are checked. Binary search must not be used on unsorted data.
Consider a binary search on the following sorted array.
How many comparisons does binary search need to find 23 in this 10-element sorted array?
Answer: (B) 3
Step 1: mid=4 (value 16). 23>16, search right half. Step 2: mid=7 (value 56). 23<56, search left half. Step 3: mid=5 (value 23). Found! Three comparisons.
Why Not the Others?
(A) The target is not at the first midpoint.
(C) Binary search eliminates half the array each step. 3 comparisons suffice.
(D) 10 comparisons would be linear search. Binary search is much faster.
Common Mistake
Binary search requires a SORTED array. It repeatedly halves the search space. For n elements, it needs at most log2(n) comparisons.
AP Exam Tip
Binary search: O(log n). Must be sorted. Each step eliminates half. For 1000 elements, at most ~10 comparisons. Know how to trace the algorithm step by step.