AP Computer Science Principles Flashcards: Binary Search

What this deck covers

This deck focuses on Binary Search, giving you a quick way to review the definitions, rules, and examples that matter most for AP Computer Science Principles.

How to use these flashcards

Work through these flashcards in short sessions. Try to answer each prompt before flipping the card, then revisit any cards you miss until the explanation feels automatic.

Flashcard 1: Is binary search applicable to all data types?

Answer: Yes, if they are comparable and sorted. Elements must support comparison operators and ordering.

Flashcard 2: State the time complexity of binary search in the worst case.

Answer: $O(\text{log } n)$. Eliminates half the search space with each comparison.

Flashcard 3: Identify the first step in performing a binary search.

Answer: Calculate the middle index of the dataset. Starting point to compare against the target value.

Flashcard 4: Which data structure is most suitable for binary search?

Answer: Sorted array or list. Allows constant-time access to any index for comparisons.

Flashcard 5: What is the space complexity of binary search?

Answer: $O(1)$. Only uses a few variables regardless of dataset size.

Flashcard 6: In binary search, if the target is greater than the middle element, what is the next step?

Answer: Search the right half of the dataset. Target must be in the larger half of the remaining elements.

Flashcard 7: What happens if the target is less than the middle element in binary search?

Answer: Search the left half of the dataset. Target must be in the smaller half of the remaining elements.

Flashcard 8: What is returned if the target element is not found in binary search?

Answer: Typically, -1 or null. Standard convention to indicate search failure.

Flashcard 9: How does binary search determine the middle element of the dataset?

Answer: Middle index = $\frac{\text{low} + \text{high}}{2}$. Formula calculates the midpoint between current boundaries.

Flashcard 10: What is a potential drawback of using binary search?

Answer: Requires a sorted dataset. Limits use to pre-sorted data structures only.

Flashcard 11: Determine the new search range if binary search finds the target.

Answer: Search ends; no new range is needed. Target found means search is complete and successful.

Flashcard 12: What is one advantage of binary search over linear search?

Answer: Faster on sorted datasets. Logarithmic vs linear time complexity provides significant speedup.

Flashcard 13: Identify a situation where binary search cannot be applied.

Answer: On an unsorted dataset. Binary search assumes sorted order to function correctly.

Flashcard 14: What kind of search is binary search considered?

Answer: A logarithmic search. Uses logarithmic time complexity for efficient searching.

Flashcard 15: Find the new middle index if low = 0 and high = 8 in binary search.

Answer: Middle index = 4. Using the formula $(0 + 8) / 2 = 4$.

Flashcard 16: Which condition ends a binary search loop?

Answer: When 'low' exceeds 'high'. Indicates no valid search range remains.

Flashcard 17: Is binary search suitable for recursive implementation?

Answer: Yes, it can be implemented recursively. Natural fit for divide-and-conquer recursive approach.

Flashcard 18: How does binary search improve efficiency compared to linear search?

Answer: By halving the search range each step. Eliminates half the possibilities with each comparison.

Flashcard 19: What is a key difference between binary and linear search?

Answer: Binary requires sorting; linear does not. Binary needs preprocessing while linear works on any order.

Flashcard 20: In binary search, what happens if 'low' equals 'high'?

Answer: Check the element at 'low' or 'high'. Single element left to verify as target match.

Flashcard 21: What is an iterative approach to implementing binary search?

Answer: Using a while loop to adjust 'low' and 'high'. Uses loops to repeatedly narrow the search boundaries.

Flashcard 22: Why is binary search not suitable for datasets with frequent updates?

Answer: Frequent sorting is required. Maintaining sorted order becomes costly with many changes.

Flashcard 23: Which programming concept is often used with binary search?

Answer: Recursion or iterative loops. Essential for implementing the divide-and-conquer strategy.

Flashcard 24: What is the impact of binary search on unsorted data?

Answer: It fails to find elements reliably. Ordering assumption is violated, breaking the algorithm.

Flashcard 25: Calculate the middle index for 'low' = 3 and 'high' = 7.

Answer: Middle index = 5. Using the formula $(3 + 7) / 2 = 5$.

Flashcard 26: What is the effect of binary search on a dataset of size 1?

Answer: Directly checks the only element. One comparison determines if target is found.

Flashcard 27: Does binary search require additional memory for its operations?

Answer: No, uses constant space $O(1)$. Only needs variables for indices, not extra arrays.

Flashcard 28: What is a common application of binary search in computer science?

Answer: Searching in databases. Efficiently locates records in sorted database indexes.

Flashcard 29: Determine the middle index for 'low' = 2, 'high' = 6.

Answer: Middle index = 4. Using the formula $(2 + 6) / 2 = 4$.

Flashcard 30: How does binary search behave on a single-element dataset?

Answer: Checks if the element is the target. Performs one comparison to determine success or failure.