AP Computer Science Principles Quiz: Binary Search

What this quiz covers

This quiz focuses on Binary Search, giving you a quick way to practice the rules, question types, and explanations that matter most for AP Computer Science Principles.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

Question 1

1. 2 iterations are required.
2. 3 iterations are required. (correct answer)
3. 6 iterations are required.
4. 9 iterations are required.

Explanation: This question tests understanding of binary search algorithm application in AP Computer Science Principles. Binary search divides a sorted array in half repeatedly to efficiently locate the target element, using the midpoint to guide each iteration. In this problem, a sorted array of strings ["adam", "bella", "carlos", "dina", "eli", "fatima", "gwen", "hugo", "ivan"] is searched for "fatima" using alphabetical comparison. Choice B is correct because exactly 3 iterations are required: first finds "eli" at mid=4, second finds "gwen" at mid=6, and third finds "fatima" at mid=5. Choice C is incorrect because it might represent a miscount or confusion with the index position of the target. To help students: Demonstrate that binary search works identically with strings using alphabetical ordering, and practice with both numeric and string examples. Watch for: students thinking string comparison works differently than numeric comparison, and ensure they understand iteration counting.

Question 2

1. Missing value 107 is identified. (correct answer)
2. Missing value 106 is identified.
3. Missing value 107 after 10 sequential checks.
4. No value is missing because the array is sorted.

Explanation: This question tests understanding of binary search algorithm application in AP Computer Science Principles. Binary search divides a sorted array in half repeatedly to efficiently locate the target element, using the midpoint to guide each iteration. In this problem, binary search is cleverly adapted to find a missing value by comparing actual array values with expected sequential values. Choice A is correct because the algorithm identifies that 107 is missing when array[6]=108 but the expected value at that position should be 107 in a complete sequence. Choice B is incorrect because 106 is present in the array at index 5 - students might misread the array or misunderstand the algorithm. To help students: Explain how binary search can be modified for different problems beyond simple element finding, and practice identifying patterns in sequences. Watch for: confusion about how the expected value is calculated and difficulty understanding this non-standard application of binary search.

Question 3

1. Position 6.
2. Position 7. (correct answer)
3. Position 8.
4. Position 5.

Explanation: This question tests understanding of binary search algorithm application in AP Computer Science Principles. Binary search divides a sorted array in half repeatedly to efficiently locate the target element, using the midpoint to guide each iteration. In this problem, we have a 10-element array (indices 0-9) searching for the value 33, which the algorithm successfully locates at index 7. Choice B is correct because it identifies position 7 where the target 33 is found: first iteration calculates mid=4 where A[4]=21<33, adjusting low=5; second iteration calculates mid=7 where A[7]=33 equals our target. Choice A is incorrect because it suggests position 6, which would contain the value 29, not our target 33. To help students: Use array diagrams with indices clearly labeled and practice converting between array indices and positions. Emphasize that in zero-indexed arrays, position numbers match index numbers.

Question 4

1. 2 iterations are required.
2. 3 iterations are required. (correct answer)
3. 4 iterations are required.
4. 12 iterations are required.

Explanation: This question tests understanding of binary search algorithm application in AP Computer Science Principles. Binary search divides a sorted array in half repeatedly to efficiently locate the target element, using the midpoint to guide each iteration. In this problem, we have a 12-element string array (indices 0-11) searching for "Mole", with the algorithm showing three distinct iterations using alphabetical comparison. Choice B is correct because it counts all three iterations: (1) mid=5, "Fox"<"Mole", adjust low=6; (2) mid=8, "Ibis"<"Mole", adjust low=9; (3) mid=10, "Mole"=target, search completes. Choice A is incorrect because it undercounts the iterations, missing one of the comparison steps needed to locate the target. To help students: Practice with string arrays to reinforce alphabetical ordering concepts. Create trace tables that clearly show each iteration's boundaries, mid calculation, and string comparison result.

Question 5

1. 3 iterations are required.
2. 4 iterations are required. (correct answer)
3. 7 iterations are required.
4. 14 iterations are required.

Explanation: This question tests understanding of binary search algorithm application in AP Computer Science Principles. Binary search divides a sorted array in half repeatedly to efficiently locate the target element, using the midpoint to guide each iteration. In this problem, the array [5, 8, 12, 17, 21, 26, 30, 34, 41, 49, 55, 63, 70, 81] is searched for 34, requiring students to count iterations carefully. Choice B is correct because exactly 4 iterations are needed: mid=6 (30), mid=10 (55), mid=8 (41), and finally mid=7 (34). Choice A is incorrect because it undercounts by one iteration - students might miss counting the final successful comparison. To help students: Create iteration tracking tables and emphasize that finding the target still counts as an iteration. Watch for: off-by-one errors in counting iterations and confusion about whether the successful find counts as an iteration.

Question 6

1. 27
2. 35 (correct answer)
3. 44
4. 50

Explanation: This question tests understanding of binary search algorithm application in AP Computer Science Principles. Binary search divides a sorted array in half repeatedly to efficiently locate the target element, using the midpoint to guide each iteration. In this problem, the array [1, 6, 9, 14, 20, 27, 35, 44, 50, 61, 73, 88, 94] has 13 elements, and students must identify the first iteration's middle element. Choice B is correct because with low=0 and high=12, the midpoint calculation ⌊(0+12)/2⌋=6 gives index 6, which contains the value 35. Choice C is incorrect because 44 is the target value at index 7, not the middle element of the first iteration - students may confuse the target with the midpoint. To help students: Always start by calculating the initial midpoint before any comparisons, and use array visualization tools to highlight the middle element. Watch for: confusion between the target value and the middle element value, and errors in initial midpoint calculation.

Question 7

1. 33
2. 39
3. 45 (correct answer)
4. 52

Explanation: This question tests understanding of binary search algorithm application in AP Computer Science Principles. Binary search divides a sorted array in half repeatedly to efficiently locate the target element, using the midpoint to guide each iteration. In this problem, the array [4, 9, 13, 18, 21, 27, 33, 39, 45, 52, 60] is searched for 45, and students must identify the middle element in the second iteration. Choice C is correct because in the second iteration with low=6 and high=10, the midpoint calculation ⌊(6+10)/2⌋=8 gives index 8, which contains the value 45. Choice B is incorrect because 39 is at index 7, not the calculated midpoint of the second iteration - students may confuse adjacent indices. To help students: Create tables showing low, high, mid values for each iteration, and practice calculating midpoints using integer division. Watch for: off-by-one errors in midpoint calculations and confusion about which iteration is being referenced.

Question 8

1. It halves the remaining search range each iteration. (correct answer)
2. It checks elements sequentially from the first entry.
3. It works best when the array is randomly ordered.
4. It requires more comparisons as the array grows.

Explanation: This question tests understanding of binary search algorithm application in AP Computer Science Principles. Binary search divides a sorted array in half repeatedly to efficiently locate the target element, using the midpoint to guide each iteration. In this problem, a phone directory demonstrates binary search on alphabetically sorted names, highlighting the algorithm's efficiency advantage. Choice A is correct because binary search's key efficiency comes from eliminating half the remaining elements with each comparison, reducing time complexity to O(log n). Choice B is incorrect because it describes linear search behavior - binary search specifically avoids sequential checking by jumping to calculated midpoints. To help students: Compare the number of steps needed for binary vs linear search on the same array, showing how the difference grows with array size. Watch for: confusion between binary and linear search behaviors, and ensure students understand the logarithmic time complexity advantage.

Question 9

1. "dog"
2. "eel" (correct answer)
3. "fox"
4. "cat"

Explanation: This question tests understanding of binary search algorithm application in AP Computer Science Principles. Binary search divides a sorted array in half repeatedly to efficiently locate the target element, using the midpoint to guide each iteration. In this problem, the sorted array of animal names demonstrates an optimal case where the target "eel" is found immediately at the first midpoint. Choice B is correct because with low=0 and high=9, the midpoint calculation ⌊(0+9)/2⌋=4 gives index 4, which contains "eel" - the target is found in just one iteration. Choice D is incorrect because "cat" is at index 2, not the calculated midpoint - students might count positions incorrectly. To help students: Emphasize that binary search can find elements in one iteration if they happen to be at the midpoint, demonstrating best-case scenarios. Watch for: miscounting array positions or assuming binary search always requires multiple iterations.

Question 10

1. 3 iterations are required.
2. 4 iterations are required. (correct answer)
3. 5 iterations are required.
4. 12 iterations are required.

Explanation: This question tests understanding of binary search algorithm application in AP Computer Science Principles. Binary search divides a sorted array in half repeatedly to efficiently locate the target element, using the midpoint to guide each iteration. In this problem, we have a 12-element sorted array (indices 0-11) and are searching for the value 18, with the algorithm clearly showing four distinct iterations. Choice B is correct because it accurately counts all four iterations: (1) mid=5, A[5]=21>18, adjust high=4; (2) mid=2, A[2]=9<18, adjust low=3; (3) mid=3, A[3]=13<18, adjust low=4; (4) mid=4, A[4]=18=target, search completes. Choice A is incorrect because it undercounts the iterations, possibly missing the final iteration where the target is found. To help students: Create a table showing iteration number, low/high values, mid calculation, and comparison result. Emphasize that finding the target still counts as an iteration, and practice with arrays of different sizes to reinforce the logarithmic nature of binary search.

Question 11

1. Position 6.
2. Position 7. (correct answer)
3. Position 8.
4. Position 4.

Explanation: This question tests understanding of binary search algorithm application in AP Computer Science Principles. Binary search divides a sorted array in half repeatedly to efficiently locate the target element, using the midpoint to guide each iteration. In this problem, we have a sorted string array with 10 elements (indices 0-9) and are searching for "Hana", which the algorithm finds at index 7. Choice B is correct because it identifies position 7 where "Hana" is located: first iteration calculates mid=4 where "Eli"<"Hana" (alphabetically), so low becomes 5; second iteration calculates mid=7 where S[7]="Hana" matches our target. Choice A is incorrect because it confuses the position with a nearby index, possibly due to an off-by-one error in understanding array indexing. To help students: Emphasize that array positions start at 0, and practice with string comparisons using alphabetical ordering. Use visual representations showing how the search space narrows with each iteration.

Question 12

1. It discards half the remaining names each iteration. (correct answer)
2. It checks every name sequentially until it matches.
3. It works best when the array is randomly ordered.
4. It requires scanning from both ends simultaneously.

Explanation: This question tests understanding of binary search algorithm application in AP Computer Science Principles. Binary search divides a sorted array in half repeatedly to efficiently locate the target element, using the midpoint to guide each iteration. In this problem, the phone book app uses binary search on a sorted name array, demonstrating the key efficiency advantage of the algorithm. Choice A is correct because it identifies the fundamental property of binary search: with each comparison, it eliminates half of the remaining search space, leading to logarithmic time complexity O(log n). Choice B is incorrect because it describes linear search, which checks every element sequentially and has O(n) time complexity. To help students: Use visual demonstrations showing how the search space shrinks exponentially with binary search versus linearly with sequential search. Calculate and compare the maximum number of iterations needed for different array sizes to reinforce the efficiency difference.

Question 13

1. A[2] = 18. (correct answer)
2. A[3] = 21.
3. A[4] = 26.
4. A[1] = 14.

Explanation: This question tests understanding of binary search algorithm application in AP Computer Science Principles. Binary search divides a sorted array in half repeatedly to efficiently locate the target element, using the midpoint to guide each iteration. In this problem, we have an 11-element array (indices 0-10) searching for 26, and after the first iteration where mid=5 and A[5]=30>26, the search space is reduced to low=0 and high=4. Choice A is correct because the next middle element calculation is mid=(0+4)/2=2, and at index 2 we find A[2]=18. Choice C is incorrect because it suggests A[4]=26, but this would be the upper bound of our search space, not the middle element. To help students: Practice calculating midpoints with various low/high combinations and emphasize integer division. Create exercises where students must identify not just the mid index but also verify the value at that index.

Question 14

1. Position 0 (index 0). (correct answer)
2. Position 1 (index 1).
3. Position 0 after 12 sequential checks.
4. The target is out of bounds, so no position exists.

Explanation: This question tests understanding of binary search algorithm application in AP Computer Science Principles. Binary search divides a sorted array in half repeatedly to efficiently locate the target element, using the midpoint to guide each iteration. In this problem, the array [10, 14, 19, 25, 28, 31, 37, 40, 46, 53, 59, 62] is searched for the smallest element 10, demonstrating how binary search handles edge cases. Choice A is correct because the target 10 is found at index 0 (position 0) after the algorithm narrows down to the leftmost element through three iterations. Choice C is incorrect because it suggests linear search behavior with 12 checks - binary search never needs to check every element. To help students: Practice with targets at array boundaries (first and last elements) to understand how binary search handles extremes. Watch for: misconceptions that binary search struggles with boundary elements or requires special handling for the first element.